home *** CD-ROM | disk | FTP | other *** search
/ Danny Amor's Online Library / Danny Amor's Online Library - Volume 1.iso / html / rfc / rfcxxxx / rfc1059 < prev    next >
Text File  |  1995-07-25  |  138KB  |  3,246 lines

  1. Network Working Group                                        D. Mills
  2. Request for Comments:  1059                    University of Delaware
  3.                                                             July 1988
  4.  
  5.                    Network Time Protocol (Version 1)
  6.                     Specification and Implementation
  7.  
  8. Status of this Memo
  9.  
  10.    This memo describes the Network Time Protocol (NTP), specifies its
  11.    formal structure and summarizes information useful for its
  12.    implementation.  NTP provides the mechanisms to synchronize time and
  13.    coordinate time distribution in a large, diverse internet operating
  14.    at rates from mundane to lightwave.  It uses a returnable-time design
  15.    in which a distributed subnet of time servers operating in a self-
  16.    organizing, hierarchical master-slave configuration synchronizes
  17.    logical clocks within the subnet and to national time standards via
  18.    wire or radio.  The servers can also redistribute reference time via
  19.    local routing algorithms and time daemons.
  20.  
  21.    The NTP architectures, algorithms and protocols which have evolved
  22.    over several years of implementation and refinement are described in
  23.    this document.  The prototype system, which has been in regular
  24.    operation in the Internet for the last two years, is described in an
  25.    Appendix along with performance data which shows that timekeeping
  26.    accuracy throughout most portions of the Internet can be ordinarily
  27.    maintained to within a few tens of milliseconds, even in cases of
  28.    failure or disruption of clocks, time servers or nets.  This is a
  29.    Draft Standard for an Elective protocol.  Distribution of this memo
  30.    is unlimited.
  31.  
  32.                              Table of Contents
  33.  
  34.    1.      Introduction                                               3
  35.    1.1.    Related Technology                                         4
  36.    2.      System Architecture                                        6
  37.    2.1.    Implementation Model                                       7
  38.    2.2.    Network Configurations                                     9
  39.    2.3.    Time Scales                                               10
  40.    3.      Network Time Protocol                                     12
  41.    3.1.    Data Formats                                              12
  42.    3.2.    State Variables and Parameters                            13
  43.    3.2.1.  Common Variables                                          15
  44.    3.2.2.  System Variables                                          17
  45.    3.2.3.  Peer Variables                                            18
  46.    3.2.4.  Packet Variables                                          19
  47.    3.2.5.  Clock Filter Variables                                    19
  48.    3.2.6.  Parameters                                                20
  49.  
  50.  
  51.  
  52. Mills                                                           [Page 1]
  53.  
  54. RFC 1059                 Network Time Protocol                 July 1988
  55.  
  56.  
  57.    3.3.    Modes of Operation                                        21
  58.    3.4.    Event Processing                                          22
  59.    3.4.1.  Timeout Procedure                                         23
  60.    3.4.2.  Receive Procedure                                         24
  61.    3.4.3.  Update Procedure                                          27
  62.    3.4.4.  Initialization Procedures                                 29
  63.    4.      Filtering and Selection Algorithms                        29
  64.    4.1.    Clock Filter Algorithm                                    29
  65.    4.2     Clock Selection Algorithm                                 30
  66.    4.3.    Variable-Rate Polling                                     32
  67.    5.      Logical Clocks                                            33
  68.    5.1.    Uniform Phase Adjustments                                 35
  69.    5.2.    Nonuniform Phase Adjustments                              36
  70.    5.3.    Maintaining Date and Time                                 37
  71.    5.4.    Calculating Estimates                                     37
  72.    6.      References                                                40
  73.  
  74.    Appendices
  75.    Appendix A. UDP Header Format                                     43
  76.    Appendix B. NTP Data Format                                       44
  77.    Appendix C. Timeteller Experiments                                47
  78.    Appendix D. Evaluation of Filtering Algorithms                    49
  79.    Appendix E. NTP Synchronization Networks                          56
  80.  
  81.    List of Figures
  82.    Figure 2.1. Implementation Model                                   8
  83.    Figure 3.1. Calculating Delay and Offset                          26
  84.    Figure 5.1. Clock Registers                                       34
  85.    Figure D.1. Calculating Delay and Offset                          50
  86.    Figure E.1. Primary Service Network                               57
  87.  
  88.    List of Tables
  89.    Table 2.1. Dates of Leap-Second Insertion                         11
  90.    Table 3.1. System Variables                                       14
  91.    Table 3.2. Peer Variables                                         14
  92.    Table 3.3. Packet Variables                                       15
  93.    Table 3.4. Parameters                                             15
  94.    Table 4.1. Outlyer Selection Procedure                            32
  95.    Table 5.1. Clock Parameters                                       35
  96.    Table C.1. Distribution Functions                                 47
  97.    Table D.1. Delay and Offset Measurements (UMD)                    52
  98.    Table D.2.a Delay and Offset Measurements (UDEL)                  52
  99.    Table D.2.b Offset Measurements (UDEL)                            53
  100.    Table D.3. Minimum Filter (UMD - NCAR)                            54
  101.    Table D.4. Median Filter (UMD - NCAR)                             54
  102.    Table D.5. Minimum Filter (UDEL - NCAR)                           55
  103.    Table E.1. Primary Servers                                        56
  104.  
  105.  
  106.  
  107.  
  108. Mills                                                           [Page 2]
  109.  
  110. RFC 1059                 Network Time Protocol                 July 1988
  111.  
  112.  
  113. 1.  Introduction
  114.  
  115.    This document describes the Network Time Protocol (NTP), including
  116.    the architectures, algorithms and protocols to synchronize local
  117.    clocks in a set of distributed clients and servers.  The protocol was
  118.    first described in RFC-958 [24], but has evolved in significant ways
  119.    since publication of that document.  NTP is built on the Internet
  120.    Protocol (IP) [10] and User Datagram Protocol (UDP) [6], which
  121.    provide a connectionless transport mechanism;  however, it is readily
  122.    adaptable to other protocol suites.  It is evolved from the Time
  123.    Protocol [13] and the ICMP Timestamp message [11], but is
  124.    specifically designed to maintain accuracy and robustness, even when
  125.    used over typical Internet paths involving multiple gateways and
  126.    unreliable nets.
  127.  
  128.    The service environment consists of the implementation model, service
  129.    model and time scale described in Section 2.  The implementation
  130.    model is based on a multiple-process operating system architecture,
  131.    although other architectures could be used as well.  The service
  132.    model is based on a returnable-time design which depends only on
  133.    measured offsets, or skews, but does not require reliable message
  134.    delivery.  The subnet is a self-organizing, hierarchical master-slave
  135.    configuration, with synchronization paths determined by a minimum-
  136.    weight spanning tree.  While multiple masters (primary servers) may
  137.    exist, there is no requirement for an election protocol.
  138.  
  139.    NTP itself is described in Section 3.  It provides the protocol
  140.    mechanisms to synchronize time in principle to precisions in the
  141.    order of nanoseconds while preserving a non-ambiguous date well into
  142.    the next century.  The protocol includes provisions to specify the
  143.    characteristics and estimate the error of the local clock and the
  144.    time server to which it may be synchronized.  It also includes
  145.    provisions for operation with a number of mutually suspicious,
  146.    hierarchically distributed primary reference sources such as radio
  147.    clocks.
  148.  
  149.    Section 4 describes algorithms useful for deglitching and smoothing
  150.    clock-offset samples collected on a continuous basis.  These
  151.    algorithms began with those suggested in [22], were refined as the
  152.    results of experiments described in [23] and further evolved under
  153.    typical operating conditions over the last two years.  In addition,
  154.    as the result of experience in operating multiple-server nets
  155.    including radio-synchronized clocks at several sites in the US and
  156.    with clients in the US and Europe, reliable algorithms for selecting
  157.    good clocks from a population possibly including broken ones have
  158.    been developed and are described in Section 4.
  159.  
  160.    The accuracies achievable by NTP depend strongly on the precision of
  161.  
  162.  
  163.  
  164. Mills                                                           [Page 3]
  165.  
  166. RFC 1059                 Network Time Protocol                 July 1988
  167.  
  168.  
  169.    the local clock hardware and stringent control of device and process
  170.    latencies.  Provisions must be included to adjust the software
  171.    logical clock time and frequency in response to corrections produced
  172.    by NTP.  Section 5 describes a logical clock design evolved from the
  173.    Fuzzball implementation described in [15].  This design includes
  174.    offset-slewing, drift-compensation and deglitching mechanisms capable
  175.    of accuracies in order of a millisecond, even after extended periods
  176.    when synchronization to primary reference sources has been lost.
  177.  
  178.    The UDP and NTP packet formats are shown in Appendices A and B.
  179.    Appendix C presents the results of a survey of about 5500 Internet
  180.    hosts showing how their clocks compare with primary reference sources
  181.    using three different time protocols, including NTP.  Appendix D
  182.    presents experimental results using several different deglitching and
  183.    smoothing algorithms.  Appendix E describes the prototype NTP primary
  184.    service net, as well as proposed rules of engagement for its use.
  185.  
  186. 1.1.  Related Technology
  187.  
  188.    Other mechanisms have been specified in the Internet protocol suite
  189.    to record and transmit the time at which an event takes place,
  190.    including the Daytime protocol [12], Time Protocol [13], ICMP
  191.    Timestamp message [11] and IP Timestamp option [9].  Experimental
  192.    results on measured times and roundtrip delays in the Internet are
  193.    discussed in [14], [23] and [31].  Other synchronization protocols
  194.    are discussed in [7], [17], [20] and [28].  NTP uses techniques
  195.    evolved from both linear and nonlinear synchronization methodology.
  196.    Linear methods used for digital telephone network synchronization are
  197.    summarized in [3], while nonlinear methods used for process
  198.    synchronization are summarized in [27].
  199.  
  200.    The Fuzzball routing protocol [15], sometimes called Hellospeak,
  201.    incorporates time synchronization directly into the routing protocol
  202.    design.  One or more processes synchronize to an external reference
  203.    source, such as a radio clock or NTP daemon, and the routing
  204.    algorithm constructs a minimum-weight spanning tree rooted on these
  205.    processes.  The clock offsets are then distributed along the arcs of
  206.    the spanning tree to all processes in the system and the various
  207.    process clocks corrected using the procedure described in Section 5
  208.    of this document.  While it can be seen that the design of Hellospeak
  209.    strongly influenced the design of NTP, Hellospeak itself is not an
  210.    Internet protocol and is unsuited for use outside its local-net
  211.    environment.
  212.  
  213.    The Unix 4.3bsd model [20] uses a single master time daemon to
  214.    measure offsets of a number of slave hosts and send periodic
  215.    corrections to them.  In this model the master is determined using an
  216.    election algorithm [25] designed to avoid situations where either no
  217.  
  218.  
  219.  
  220. Mills                                                           [Page 4]
  221.  
  222. RFC 1059                 Network Time Protocol                 July 1988
  223.  
  224.  
  225.    master is elected or more than one master is elected.  The election
  226.    process requires a broadcast capability, which is not a ubiquitous
  227.    feature of the Internet.  While this model has been extended to
  228.    support hierarchical configurations in which a slave on one network
  229.    serves as a master on the other [28], the model requires handcrafted
  230.    configuration tables in order to establish the hierarchy and avoid
  231.    loops.  In addition to the burdensome, but presumably infrequent,
  232.    overheads of the election process, the offset measurement/correction
  233.    process requires twice as many messages as NTP per update.
  234.  
  235.    A good deal of research has gone into the issue of maintaining
  236.    accurate time in a community where some clocks cannot be trusted.  A
  237.    truechimer is a clock that maintains timekeeping accuracy to a
  238.    previously published (and trusted) standard, while a falseticker is a
  239.    clock that does not.  Determining whether a particular clock is a
  240.    truechimer or falseticker is an interesting abstract problem which
  241.    can be attacked using methods summarized in [19] and [27].
  242.  
  243.    A convergence function operates upon the offsets between the clocks
  244.    in a system to increase the accuracy by reducing or eliminating
  245.    errors caused by falsetickers.  There are two classes of convergence
  246.    functions, those involving interactive convergence algorithms and
  247.    those involving interactive consistency algorithms.  Interactive
  248.    convergence algorithms use statistical clustering techniques such as
  249.    the fault-tolerant average algorithm of [17], the CNV algorithm of
  250.    [19], the majority-subset algorithm of [22], the egocentric algorithm
  251.    of [27] and the algorithms in Section 4 of this document.
  252.  
  253.    Interactive consistency algorithms are designed to detect faulty
  254.    clock processes which might indicate grossly inconsistent offsets in
  255.    successive readings or to different readers.  These algorithms use an
  256.    agreement protocol involving successive rounds of readings, possibly
  257.    relayed and possibly augmented by digital signatures.  Examples
  258.    include the fireworks algorithm of [17] and the optimum algorithm of
  259.    [30].  However, these algorithms require large numbers of messages,
  260.    especially when large numbers of clocks are involved, and are
  261.    designed to detect faults that have rarely been found in the Internet
  262.    experience.  For these reasons they are not considered further in
  263.    this document.
  264.  
  265.    In practice it is not possible to determine the truechimers from the
  266.    falsetickers on other than a statistical basis, especially with
  267.    hierarchical configurations and a statistically noisy Internet.
  268.    Thus, the approach taken in this document and its predecessors
  269.    involves mutually coupled oscillators and maximum-likelihood
  270.    estimation and selection procedures.  From the analytical point of
  271.    view, the system of distributed NTP peers operates as a set of
  272.    coupled phase-locked oscillators, with the update algorithm
  273.  
  274.  
  275.  
  276. Mills                                                           [Page 5]
  277.  
  278. RFC 1059                 Network Time Protocol                 July 1988
  279.  
  280.  
  281.    functioning as a phase detector and the logical clock as a voltage-
  282.    controlled oscillator.  This similarity is not accidental, since
  283.    systems like this have been studied extensively [3], [4] and [5].
  284.  
  285.    The particular choice of offset measurement and computation procedure
  286.    described in Section 3 is a variant of the returnable-time system
  287.    used in some digital telephone networks [3].  The clock filter and
  288.    selection algorithms are designed so that the clock synchronization
  289.    subnet self-organizes into a hierarchical master-slave configuration
  290.    [5].  What makes the NTP model unique is the adaptive configuration,
  291.    polling, filtering and selection functions which tailor the dynamics
  292.    of the system to fit the ubiquitous Internet environment.
  293.  
  294. 2.  System Architecture
  295.  
  296.    The purpose of NTP is to connect a number of primary reference
  297.    sources, synchronized to national standards by wire or radio, to
  298.    widely accessible resources such as backbone gateways.  These
  299.    gateways, acting as primary time servers, use NTP between them to
  300.    cross-check the clocks and mitigate errors due to equipment or
  301.    propagation failures.  Some number of local-net hosts or gateways,
  302.    acting as secondary time servers, run NTP with one or more of the
  303.    primary servers.  In order to reduce the protocol overhead the
  304.    secondary servers distribute time via NTP to the remaining local-net
  305.    hosts.  In the interest of reliability, selected hosts can be
  306.    equipped with less accurate but less expensive radio clocks and used
  307.    for backup in case of failure of the primary and/or secondary servers
  308.    or communication paths between them.
  309.  
  310.    There is no provision for peer discovery, acquisition, or
  311.    authentication in NTP.  Data integrity is provided by the IP and UDP
  312.    checksums.  No circuit-management, duplicate-detection or
  313.    retransmission facilities are provided or necessary.  The service can
  314.    operate in a symmetric mode, in which servers and clients are
  315.    indistinguishable, yet maintain a small amount of state information,
  316.    or in client/server mode, in which servers need maintain no state
  317.    other than that contained in the client request.  A lightweight
  318.    association-management capability, including dynamic reachability and
  319.    variable polling rate mechanisms, is included only to manage the
  320.    state information and reduce resource requirements.  Since only a
  321.    single NTP message format is used, the protocol is easily implemented
  322.    and can be used in a variety of solicited or unsolicited polling
  323.    mechanisms.
  324.  
  325.    It should be recognized that clock synchronization requires by its
  326.    nature long periods and multiple comparisons in order to maintain
  327.    accurate timekeeping.  While only a few measurements are usually
  328.    adequate to reliably determine local time to within a second or so,
  329.  
  330.  
  331.  
  332. Mills                                                           [Page 6]
  333.  
  334. RFC 1059                 Network Time Protocol                 July 1988
  335.  
  336.  
  337.    periods of many hours and dozens of measurements are required to
  338.    resolve oscillator drift and maintain local time to the order of a
  339.    millisecond.  Thus, the accuracy achieved is directly dependent on
  340.    the time taken to achieve it.  Fortunately, the frequency of
  341.    measurements can be quite low and almost always non-intrusive to
  342.    normal net operations.
  343.  
  344. 2.1.  Implementation Model
  345.  
  346.    In what may be the most common client/server model a client sends an
  347.    NTP message to one or more servers and processes the replies as
  348.    received.  The server interchanges addresses and ports, overwrites
  349.    certain fields in the message, recalculates the checksum and returns
  350.    the message immediately.  Information included in the NTP message
  351.    allows the client to determine the server time with respect to local
  352.    time and adjust the logical clock accordingly.  In addition, the
  353.    message includes information to calculate the expected timekeeping
  354.    accuracy and reliability, thus select the best from possibly several
  355.    servers.
  356.  
  357.    While the client/server model may suffice for use on local nets
  358.    involving a public server and perhaps many workstation clients, the
  359.    full generality of NTP requires distributed participation of a number
  360.    of client/servers or peers arranged in a dynamically reconfigurable,
  361.    hierarchically distributed configuration.  It also requires
  362.    sophisticated algorithms for association management, data
  363.    manipulation and logical clock control.  Figure 2.1 shows a possible
  364.    implementation model including four processes sharing a partitioned
  365.    data base, with a partition dedicated to each peer and interconnected
  366.    by a message-passing system.
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388. Mills                                                           [Page 7]
  389.  
  390. RFC 1059                 Network Time Protocol                 July 1988
  391.  
  392.  
  393.                                 +---------+
  394.                                 | Update  |
  395.                      +--------->|         +----------+
  396.                      |          |Algorithm|          |
  397.                      |          +----+----+          |
  398.                      |               |               |
  399.                      |               V               V
  400.                 +----+----+     +---------+     +---------+
  401.                 |         |     |  Local  |     |         |
  402.                 | Receive |     |         +---->| Timeout |
  403.                 |         |     |  Clock  |     |         |
  404.                 +---------+     +---------+     +-+-----+-+
  405.                   A     A                         |     |
  406.                   |     |                         V     V
  407.                 ===========================================
  408.                    Peers          Network          Peers
  409.  
  410.                      Figure 2.1. Implementation Model
  411.  
  412.    The timeout process, driven by independent timers for each peer,
  413.    collects information in the data base and sends NTP messages to other
  414.    peers in the net.  Each message contains the local time the message
  415.    is sent, together with previously received information and other
  416.    information necessary to compute the estimated error and manage the
  417.    association.  The message transmission rate is determined by the
  418.    accuracy expected of the local system, as well as its peers.
  419.  
  420.    The receive process receives NTP messages and perhaps messages in
  421.    other protocols as well, including ICMP, other UDP or TCP time
  422.    protocols, local-net protocols and directly connected radio clocks.
  423.    When an NTP message is received the offset between the sender clock
  424.    and the local clock is computed and incorporated into the data base
  425.    along with other information useful for error estimation and clock
  426.    selection.
  427.  
  428.    The update algorithm is initiated upon receipt of a message and at
  429.    other times.  It processes the offset data from each peer and selects
  430.    the best peer using algorithms such as those described in Section 4.
  431.    This may involve many observations of a few clocks or a few
  432.    observations of many clocks, depending on the accuracies required.
  433.  
  434.    The local clock process operates upon the offset data produced by the
  435.    update algorithm and adjusts the phase and frequency of the logical
  436.    clock using mechanisms such as described in Section 5.  This may
  437.    result in either a step change or a gradual slew adjustment of the
  438.    logical clock to reduce the offset to zero.  The logical clock
  439.    provides a stable source of time information to other users of the
  440.    system and for subsequent reference by NTP itself.
  441.  
  442.  
  443.  
  444. Mills                                                           [Page 8]
  445.  
  446. RFC 1059                 Network Time Protocol                 July 1988
  447.  
  448.  
  449. 2.2.  Network Configurations
  450.  
  451.    A primary time server is connected to a primary reference source,
  452.    usually a radio clock synchronized to national standard time.  A
  453.    secondary time server derives time synchronization, possibly via
  454.    other secondary servers, from a primary server.  Under normal
  455.    circumstances it is intended that a subnet of primary and secondary
  456.    servers assumes a hierarchical master-slave configuration with the
  457.    more accurate servers near the top and the less accurate below.
  458.  
  459.    Following conventions established by the telephone industry, the
  460.    accuracy of each server is defined by a number called its stratum,
  461.    with the stratum of a primary server assigned as one and each level
  462.    downwards in the hierarchy assigned as one greater than the preceding
  463.    level.  With current technology and available receiving equipment,
  464.    single-sample accuracies in the order of a millisecond can be
  465.    achieved at the radio clock interface and in the order of a few
  466.    milliseconds at the packet interface to the net.  Accuracies of this
  467.    order require special care in the design and implementation of the
  468.    operating system, such as described in [15], and the logical clock
  469.    mechanism, such as described in Section 5.
  470.  
  471.    As the stratum increases from one, the single-sample accuracies
  472.    achievable will degrade depending on the communication paths and
  473.    local clock stabilities.  In order to avoid the tedious calculations
  474.    [4] necessary to estimate errors in each specific configuration, it
  475.    is useful to assume the errors accumulate approximately in proportion
  476.    to the minimum total roundtrip path delay between each server and the
  477.    primary reference source to which it is synchronized.  This is called
  478.    the synchronization distance.
  479.  
  480.    Again drawing from the experience of the telephone industry, who
  481.    learned such lessons at considerable cost, the synchronization paths
  482.    should be organized to produce the highest accuracies, but must never
  483.    be allowed to form a loop.  The clock filter and selection algorithms
  484.    used in NTP accomplish this by using a variant of the Bellman-Ford
  485.    distributed routing algorithm [29] to compute the minimum-weight
  486.    spanning trees rooted on the primary servers.  This results in each
  487.    server operating at the lowest stratum and, in case of multiple peers
  488.    at the same stratum, at the lowest synchronization distance.
  489.  
  490.    As a result of the above design, the subnet reconfigures
  491.    automatically in a hierarchical master-slave configuration to produce
  492.    the most accurate time, even when one or more primary or secondary
  493.    servers or the communication paths between them fail.  This includes
  494.    the case where all normal primary servers (e.g.,  backbone WWVB
  495.    clocks) on a possibly partitioned subnet fail, but one or more backup
  496.    primary servers (e.g., local WWV clocks) continue operation.
  497.  
  498.  
  499.  
  500. Mills                                                           [Page 9]
  501.  
  502. RFC 1059                 Network Time Protocol                 July 1988
  503.  
  504.  
  505.    However, should all primary servers throughout the subnet fail, the
  506.    remaining secondary servers will synchronize among themselves for
  507.    some time and then gradually drop off the subnet and coast using
  508.    their last offset and frequency computations.  Since these
  509.    computations are expected to be very precise, especially in
  510.    frequency, even extend outage periods of a day or more should result
  511.    in timekeeping errors of not over a few tens of milliseconds.
  512.  
  513.    In the case of multiple primary servers, the spanning-tree
  514.    computation will usually select the server at minimum synchronization
  515.    distance.  However, when these servers are at approximately the same
  516.    distance, the computation may result in random selections among them
  517.    as the result of normal dispersive delays.  Ordinarily this does not
  518.    degrade accuracy as long as any discrepancy between the primary
  519.    servers is small compared to the synchronization distance.  If not,
  520.    the filter and selection algorithms will select the best of the
  521.    available servers and cast out outlyers as intended.
  522.  
  523. 2.3.  Time Scales
  524.  
  525.    Since 1972 the various national time scales have been based on
  526.    International Atomic Time (TA), which is currently maintained using
  527.    multiple cesium-beam clocks to an accuracy of a few parts in 10^12.
  528.    The Bureau International de l'Heure (BIH) uses astronomical
  529.    observations provided by the US Naval Observatory and other
  530.    observatories to determine corrections for small changes in the mean
  531.    rotation period of the Earth.  This results in Universal Coordinated
  532.    Time (UTC), which is presently decreasing from TA at a fraction of a
  533.    second per year.  When the magnitude of the correction approaches 0.7
  534.    second, a leap second is inserted or deleted in the UTC time scale on
  535.    the last day of June or December.  Further information on time scales
  536.    can be found in [26].
  537.  
  538.    For the most precise coordination and timestamping of events since
  539.    1972 it is necessary to know when leap seconds were inserted or
  540.    deleted in UTC and how the seconds are numbered.  A leap second is
  541.    inserted following second 23:59:59 on the last day of June or
  542.    December and becomes second 23:59:60 of that day.  A leap second
  543.    would be deleted by omitting second 23:59:59 on one of these days,
  544.    although this has never happened.  Leap seconds were inserted on the
  545.    following fourteen occasions prior to January 1988 (courtesy US Naval
  546.    Observatory):
  547.  
  548.  
  549.  
  550.  
  551.  
  552.  
  553.  
  554.  
  555.  
  556. Mills                                                          [Page 10]
  557.  
  558. RFC 1059                 Network Time Protocol                 July 1988
  559.  
  560.  
  561.            1  June 1972                    8  December 1978
  562.            2  December 1972                9  December 1979
  563.            3  December 1973                10 June 1981
  564.            4  December 1974                11 June 1982
  565.            5  December 1975                12 June 1983
  566.            6  December 1976                13 June 1985
  567.            7  December 1977                14 December 1987
  568.  
  569.                  Table 2.1. Dates of Leap-Second Insertion
  570.  
  571.    Like UTC, NTP operates with an abstract oscillator synchronized in
  572.    frequency to the TA time scale.  At 0000 hours on 1 January 1972 the
  573.    NTP time scale was set to 2,272,060,800, representing the number of
  574.    TA seconds since 0000 hours on 1 January 1900.  The insertion of leap
  575.    seconds in UTC does not affect the oscillator itself, only the
  576.    translation between TA and UTC, or conventional civil time.  However,
  577.    since the only institutional memory assumed by NTP is the UTC radio
  578.    broadcast service, the NTP time scale is in effect reset to UTC as
  579.    each offset estimate is computed.  When a leap second is inserted in
  580.    UTC and subsequently in NTP, knowledge of all previous leap seconds
  581.    is lost.  Thus, if a clock synchronized to NTP in early 1988 was used
  582.    to establish the time of an event that occured in early 1972, it
  583.    would be fourteen seconds early.
  584.  
  585.    When NTP is used to measure intervals between events that straddle a
  586.    leap second, special considerations apply.  When it is necessary to
  587.    determine the elapsed time between events, such as the half life of a
  588.    proton, NTP timestamps of these events can be used directly.  When it
  589.    is necessary to establish the order of events relative to UTC, such
  590.    as the order of funds transfers, NTP timestamps can also be used
  591.    directly; however, if it is necessary to establish the elapsed time
  592.    between events relative to UTC, such as the intervals between
  593.    payments on a mortgage, NTP timestamps must be converted to UTC using
  594.    the above table and its successors.
  595.  
  596.    The current formats used by NBS radio broadcast services [2] do not
  597.    include provisions for advance notice of leap seconds, so this
  598.    information must be determined from other sources.  NTP includes
  599.    provisions to distribute advance warnings of leap seconds using the
  600.    Leap Indicator bits described in Section 3.  The protocol is designed
  601.    so that these bits can be set manually at the primary clocks and then
  602.    automatically distributed throughout the system for delivery to all
  603.    logical clocks and then effected as described in Section 5.
  604.  
  605.  
  606.  
  607.  
  608.  
  609.  
  610.  
  611.  
  612. Mills                                                          [Page 11]
  613.  
  614. RFC 1059                 Network Time Protocol                 July 1988
  615.  
  616.  
  617. 3.  Network Time Protocol
  618.  
  619.    This section consists of a formal definition of the Network Time
  620.    Protocol, including its data formats, entities, state variables,
  621.    events and event-processing procedures.  The specification model is
  622.    based on the implementation model illustrated in Figure 2.1, but it
  623.    is not intended that this model is the only one upon which a
  624.    specification can be based.  In particular, the specification is
  625.    intended to illustrate and clarify the intrinsic operations of NTP
  626.    and serve as a foundation for a more rigorous, comprehensive and
  627.    verifiable specification.
  628.  
  629. 3.1.  Data Formats
  630.  
  631.    All mathematical operations expressed or implied herein are in
  632.    two's-complement arithmetic.  Data are specified as integer or
  633.    fixed-point quantities.  Since various implementations would be
  634.    expected to scale externally derived quantities for internal use,
  635.    neither the precision nor decimal-point placement for fixed-point
  636.    quantities is specified.  Unless specified otherwise, all quantities
  637.    are unsigned and may occupy the full field width, if designated, with
  638.    an implied zero preceding the most significant (leftmost) bit.
  639.    Hardware and software packages designed to work with signed
  640.    quantities will thus yield surprising results when the most
  641.    significant (sign) bit is set.  It is suggested that externally
  642.    derived, unsigned fixed-point quantities such as timestamps be
  643.    shifted right one bit for internal use, since the precision
  644.    represented by the full field width is seldom justified.
  645.  
  646.    Since NTP timestamps are cherished data and, in fact, represent the
  647.    main product of the protocol, a special timestamp format has been
  648.    established.  NTP timestamps are represented as a 64-bit unsigned
  649.    fixed-point number, in seconds relative to 0000 UT on 1 January 1900.
  650.    The integer part is in the first 32 bits and the fraction part in the
  651.    last 32 bits, as shown in the following diagram.
  652.  
  653.       0                   1                   2                   3
  654.       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  655.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  656.      |                         Integer Part                          |
  657.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  658.      |                         Fraction Part                         |
  659.      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  660.  
  661.    This format allows convenient multiple-precision arithmetic and
  662.    conversion to Time Protocol representation (seconds), but does
  663.    complicate the conversion to ICMP Timestamp message representation
  664.    (milliseconds).  The precision of this representation is about 0.2
  665.  
  666.  
  667.  
  668. Mills                                                          [Page 12]
  669.  
  670. RFC 1059                 Network Time Protocol                 July 1988
  671.  
  672.  
  673.    nanosecond, which should be adequate for even the most exotic
  674.    requirements.
  675.  
  676.    Timestamps are determined by copying the current value of the logical
  677.    clock to a timestamp variable when some significant event, such as
  678.    the arrival of a message, occurs.  In order to maintain the highest
  679.    accuracy, it is important that this be done as close to the hardware
  680.    or software driver associated with the event as possible.  In
  681.    particular, departure timestamps should be redetermined for each
  682.    link-level retransmission.  In some cases a particular timestamp may
  683.    not be available, such as when the host is rebooted or the protocol
  684.    first starts up.  In these cases the 64-bit field is set to zero,
  685.    indicating the value is invalid or undefined.
  686.  
  687.    Note that since some time in 1968 the most significant bit (bit 0 of
  688.    the Integer Part) has been set and that the 64-bit field will
  689.    overflow some time in 2036.  Should NTP be in use in 2036, some
  690.    external means will be necessary to qualify time relative to 1900 and
  691.    time relative to 2036 (and other multiples of 136 years).
  692.    Timestamped data requiring such qualification will be so precious
  693.    that appropriate means should be readily available.  There will exist
  694.    an 0.2-nanosecond interval, henceforth ignored, every 136 years when
  695.    the 64-bit field will be zero and thus considered invalid.
  696.  
  697. 3.2.  State Variables and Parameters
  698.  
  699.    Following is a tabular summary of the various state variables and
  700.    parameters used by the protocol.  They are separated into classes of
  701.    system variables, which relate to the operating system environment
  702.    and logical clock mechanism;  peer variables, which are specific to
  703.    each peer operating in symmetric mode or client mode;  packet
  704.    variables, which represent the contents of the NTP message;  and
  705.    parameters, which are fixed in all implementations of the current
  706.    version.  For each class the description of the variable is followed
  707.    by its name and the procedure or value which controls it.  Note that
  708.    variables are in lower case, while parameters are in upper case.
  709.  
  710.  
  711.  
  712.  
  713.  
  714.  
  715.  
  716.  
  717.  
  718.  
  719.  
  720.  
  721.  
  722.  
  723.  
  724. Mills                                                          [Page 13]
  725.  
  726. RFC 1059                 Network Time Protocol                 July 1988
  727.  
  728.  
  729.         System Variables                Name            Control
  730.         -------------------------------------------------------
  731.         Logical Clock                   sys.clock       update
  732.         Clock Source                    sys.peer        selection
  733.                                                         algorithm
  734.         Leap Indicator                  sys.leap        update
  735.         Stratum                         sys.stratum     update
  736.         Precision                       sys.precision   system
  737.         Synchronizing Distance          sys.distance    update
  738.         Estimated Drift Rate            sys.drift       system
  739.         Reference Clock Identifier      sys.refid       update
  740.         Reference Timestamp             sys.reftime     update
  741.  
  742.                         Table 3.1. System Variables
  743.  
  744.         Peer Variables                  Name            Control
  745.         -------------------------------------------------------
  746.         Peer Address                    peer.srcadr     system
  747.         Peer Port                       peer.srcport    system
  748.         Local Address                   peer.dstadr     system
  749.         Local Port                      peer.dstport    system
  750.         Peer State                      peer.state      receive,
  751.                                                         transmit
  752.         Reachability Register           peer.reach      receive,
  753.                                                         transmit
  754.         Peer Timer                      peer.timer      system
  755.         Timer Threshold                 peer.threshold  system
  756.         Leap Indicator                  peer.leap       receive
  757.         Stratum                         peer.stratum    receive
  758.         Peer Poll Interval              peer.ppoll      receive
  759.         Host Poll Interval              peer.hpoll      receive,
  760.                                                         transmit
  761.         Precision                       peer.precision  receive
  762.         Synchronizing Distance          peer.distance   receive
  763.         Estimated Drift Rate            peer.drift      receive
  764.         Reference Clock Identifier      peer.refid      receive
  765.         Reference Timestamp             peer.reftime    receive
  766.         Originate Timestamp             peer.org        receive
  767.         Receive Timestamp               peer.rec        receive
  768.         Filter Register                 peer.filter     filter
  769.                                                         algorithm
  770.         Delay Estimate                  peer.delay      filter
  771.                                                         algorithm
  772.         Offset Estimate                 peer.offset     filter
  773.                                                         algorithm
  774.         Dispersion Estimate             peer.dispersion filter
  775.  
  776.                          Table 3.2. Peer Variables
  777.  
  778.  
  779.  
  780. Mills                                                          [Page 14]
  781.  
  782. RFC 1059                 Network Time Protocol                 July 1988
  783.  
  784.  
  785.         Packet Variables                Name            Control
  786.         -------------------------------------------------------
  787.         Peer Address                    pkt.srcadr      transmit
  788.         Peer Port                       pkt.srcport     transmit
  789.         Local Address                   pkt.dstadr      transmit
  790.         Local Port                      pkt.dstport     transmit
  791.         Leap Indicator                  pkt.leap        transmit
  792.         Version Number                  pkt.version     transmit
  793.         Stratum                         pkt.stratum     transmit
  794.         Poll                            pkt.poll        transmit
  795.         Precision                       pkt.precision   transmit
  796.         Synchronizing Distance          pkt.distance    transmit
  797.         Estimated Drift Rate            pkt.drift       transmit
  798.         Reference Clock Identifier      pkt.refid       transmit
  799.         Reference Timestamp             pkt.reftime     transmit
  800.         Originate Timestamp             pkt.org         transmit
  801.         Receive Timestamp               pkt.rec         transmit
  802.         Transmit Timestamp              pkt.xmt         transmit
  803.  
  804.                         Table 3.3. Packet Variables
  805.  
  806.         Parameters                      Name            Value
  807.         -------------------------------------------------------
  808.         NTP Version                     NTP.VERSION     1
  809.         NTP Port                        NTP.PORT        123
  810.         Minimum Polling Interval        NTP.MINPOLL     6 (64 sec)
  811.         Maximum Polling Interval        NTP.MAXPOLL     10 (1024
  812.                                                         sec)
  813.         Maximum Dispersion              NTP.MAXDISP     65535 ms
  814.         Reachability Register Size      PEER.WINDOW     8
  815.         Shift Register Size             PEER.SHIFT      4/8
  816.         Dispersion Threshold            PEER.THRESHOLD  500 ms
  817.         Filter Weight                   PEER.FILTER     .5
  818.         Select Weight                   PEER.SELECT     .75
  819.  
  820.                            Table 3.4. Parameters
  821.  
  822.    Following is a description of the various variables used in the
  823.    protocol.  Additional details on formats and use are presented in
  824.    later sections and appendices.
  825.  
  826. 3.2.1.  Common Variables
  827.  
  828.    The following variables are common to the system, peer and packet
  829.    classes.
  830.  
  831.    Peer Address (peer.srcadr, pkt.srcadr) Peer Port (peer.srcport,
  832.    pkt.srcport)
  833.  
  834.  
  835.  
  836. Mills                                                          [Page 15]
  837.  
  838. RFC 1059                 Network Time Protocol                 July 1988
  839.  
  840.  
  841.       These are the 32-bit Internet address and 16-bit port number of
  842.       the remote host.
  843.  
  844.    Local Address (peer.dstadr, pkt.dstadr) Local Port (peer.dstport,
  845.    pkt.dstport)
  846.  
  847.       These are the 32-bit Internet address and 16-bit port number of
  848.       the local host.  They are included among the state variables to
  849.       support multi-homing.
  850.  
  851.    Leap Indicator (sys.leap, peer.leap, pkt.leap)
  852.  
  853.       This is a two-bit code warning of an impending leap second to be
  854.       inserted in the NTP time scale.  The bits are set before 23:59 on
  855.       the day of insertion and reset after 00:01 on the following day.
  856.       This causes the number of seconds (rollover interval) in the day
  857.       of insertion to be increased or decreased by one.  In the case of
  858.       primary servers the bits are set by operator intervention, while
  859.       in the case of secondary servers the bits are set by the protocol.
  860.       The two bits are coded as follows:
  861.  
  862.                    00      no warning (day has 86400 seconds)
  863.                    01      +1 second (day has 86401 seconds)
  864.                            seconds)
  865.                    10      -1 second (day has 86399 seconds)
  866.                            seconds)
  867.                    11      alarm condition (clock not synchronized)
  868.  
  869.       In all except the alarm condition (11) NTP itself does nothing
  870.       with these bits, except pass them on to the time-conversion
  871.       routines that are not part of NTP.  The alarm condition occurs
  872.       when, for whatever reason, the logical clock is not synchronized,
  873.       such as when first coming up or after an extended period when no
  874.       outside reference source is available.
  875.  
  876.    Stratum (sys.stratum, peer.stratum, pkt.stratum)
  877.  
  878.       This is an integer indicating the stratum of the logical clock.  A
  879.       value of zero is interpreted as unspecified, one as a primary
  880.       clock (synchronized by outside means) and remaining values as the
  881.       stratum level (synchronized by NTP).  For comparison purposes a
  882.       value of zero is considered greater than any other value.
  883.  
  884.    Peer Poll Interval (peer.ppoll, pkt.poll)
  885.  
  886.       This is a signed integer used only in symmetric mode and
  887.       indicating the minimum interval between messages sent to the peer,
  888.       in seconds as a power of two.  For instance, a value of six
  889.  
  890.  
  891.  
  892. Mills                                                          [Page 16]
  893.  
  894. RFC 1059                 Network Time Protocol                 July 1988
  895.  
  896.  
  897.       indicates a minimum interval of 64 seconds.  The value of this
  898.       variable must not be less than NTP.MINPOLL and must not be greater
  899.       than NTP.MAXPOLL.
  900.  
  901.    Precision (sys.precision, peer.precision, pkt.precision)
  902.  
  903.       This is a signed integer indicating the precision of the logical
  904.       clock, in seconds to the nearest power of two.  For instance, a
  905.       60-Hz line-frequency clock would be assigned the value -6, while a
  906.       1000-Hz crystal-derived clock would be assigned the value -10.
  907.  
  908.    Synchronizing Distance (sys.distance, peer.distance, pkt.distance)
  909.  
  910.       This is a fixed-point number indicating the estimated roundtrip
  911.       delay to the primary clock, in seconds.
  912.  
  913.  
  914.    Estimated Drift Rate (sys.drift, peer.drift, pkt.drift)
  915.  
  916.       This is a fixed-point number indicating the estimated drift rate
  917.       of the local clock, in dimensionless units.
  918.  
  919.    Reference Clock Identifier (sys.refid, peer.refid, pkt.refid)
  920.  
  921.       This is a code identifying the particular reference clock or
  922.       server.  The interpretation of the value depends on the stratum.
  923.       For stratum values of zero (unspecified) or one (primary clock),
  924.       the value is an ASCII string identifying the reason or clock,
  925.       respectively.  For stratum values greater than one (synchronized
  926.       by NTP), the value is the 32-bit Internet address of the reference
  927.       server.
  928.  
  929.    Reference Timestamp (sys.reftime, peer.reftime, pkt.reftime)
  930.  
  931.       This is the local time, in timestamp format, when the logical
  932.       clock was last updated.  If the logical clock has never been
  933.       synchronized, the value is zero.
  934.  
  935. 3.2.2.  System Variables
  936.  
  937.    The following variables are used by the operating system in order to
  938.    synchronize the logical clock.
  939.  
  940.    Logical Clock (sys.clock)
  941.  
  942.       This is the current local time, in timestamp format.  Local time
  943.       is derived from the hardware clock of the particular machine and
  944.       increments at intervals depending on the design used.  An
  945.  
  946.  
  947.  
  948. Mills                                                          [Page 17]
  949.  
  950. RFC 1059                 Network Time Protocol                 July 1988
  951.  
  952.  
  953.       appropriate design, including slewing and drift-compensation
  954.       mechanisms, is described in Section 5.
  955.  
  956.    Clock Source (sys.peer)
  957.  
  958.       This is a selector identifying the current clock source.  Usually
  959.       this will be a pointer to a structure containing the peer
  960.       variables.
  961.  
  962. 3.2.3.  Peer Variables
  963.  
  964.    Following is a list of state variables used by the peer management
  965.    and measurement functions.  There is one set of these variables for
  966.    every peer operating in client mode or symmetric mode.
  967.  
  968.    Peer State (peer.state)
  969.  
  970.       This is a bit-encoded quantity used for various control functions.
  971.  
  972.    Host Poll Interval (peer.hpoll)
  973.  
  974.       This is a signed integer used only in symmetric mode and
  975.       indicating the minimum interval between messages expected from the
  976.       peer, in seconds as a power of two.  For instance, a value of six
  977.       indicates a minimum interval of 64 seconds.  The value of this
  978.       variable must not be less than NTP.MINPOLL and must not be greater
  979.       than NTP.MAXPOLL.
  980.  
  981.    Reachability Register (peer.reach)
  982.  
  983.       This is a code used to determine the reachability status of the
  984.       peer.  It is used as a shift register, with bits entering from the
  985.       least significant (rightmost) end.  The size of this register is
  986.       specified as PEER.SHIFT bits.
  987.  
  988.    Peer Timer (peer.timer)
  989.  
  990.       This is an integer counter used to control the interval between
  991.       transmitted NTP messages.
  992.  
  993.    Timer Threshold (peer.threshold)
  994.  
  995.       This is the timer value which, when reached, causes the timeout
  996.       procedure to be executed.
  997.  
  998.    Originate Timestamp (peer.org, pkt.org)
  999.  
  1000.       This is the local time, in timestamp format, at the peer when its
  1001.  
  1002.  
  1003.  
  1004. Mills                                                          [Page 18]
  1005.  
  1006. RFC 1059                 Network Time Protocol                 July 1988
  1007.  
  1008.  
  1009.       latest NTP message was sent.  If the peer becomes unreachable the
  1010.       value is set to zero.
  1011.  
  1012.    Receive Timestamp (peer.rec, pkt.rec)
  1013.  
  1014.       This is the local time, in timestamp format, when the latest NTP
  1015.       message from the peer arrived.  If the peer becomes unreachable
  1016.       the value is set to zero.
  1017.  
  1018. 3.2.4.  Packet Variables
  1019.  
  1020.    Following is a list of variables used in NTP messages in addition to
  1021.    the common variables above.
  1022.  
  1023.    Version Number (pkt.version)
  1024.  
  1025.       This is an integer indicating the version number of the sender.
  1026.       NTP messages will always be sent with the current version number
  1027.       NTP.VERSION and will always be accepted if the version number
  1028.       matches NTP.VERSION.  Exceptions may be advised on a case-by-case
  1029.       basis at times when the version number is changed.
  1030.  
  1031.    Transmit Timestamp (pkt.xmt)
  1032.  
  1033.       This is the local time, in timestamp format, at which the NTP
  1034.       message departed the sender.
  1035.  
  1036. 3.2.5.  Clock Filter Variables
  1037.  
  1038.    When the filter and selection algorithms suggested in Section 4 are
  1039.    used, the following state variables are defined.  There is one set of
  1040.    these variables for every peer operating in client mode or symmetric
  1041.    mode.
  1042.  
  1043.    Filter Register (peer.filter)
  1044.  
  1045.       This is a shift register of PEER.WINDOW bits, where each stage is
  1046.       a tuple consisting of the measured delay concatenated with the
  1047.       measured offset associated with a single observation.
  1048.       Delay/offset observations enter from the least significant
  1049.       (rightmost) right and are shifted towards the most significant
  1050.       (leftmost) end and eventually discarded as new observations
  1051.       arrive.  The register is cleared to zeros when (a) the peer
  1052.       becomes unreachable or (b) the logical clock has just been reset
  1053.       so as to cause a significant discontinuity in local time.
  1054.  
  1055.  
  1056.  
  1057.  
  1058.  
  1059.  
  1060. Mills                                                          [Page 19]
  1061.  
  1062. RFC 1059                 Network Time Protocol                 July 1988
  1063.  
  1064.  
  1065.    Delay Estimate (peer.delay)
  1066.  
  1067.       This is a signed, fixed-point number indicating the latest delay
  1068.       estimate output from the filter, in seconds.  While the number is
  1069.       signed, only those values greater than zero represent valid delay
  1070.       estimates.
  1071.  
  1072.    Offset Estimate (peer.offset)
  1073.  
  1074.       This is a signed, fixed-point number indicating the latest offset
  1075.       estimate output from the filter, in seconds.
  1076.  
  1077.    Dispersion Estimate (peer.dispersion)
  1078.  
  1079.       This is a fixed-point number indicating the latest dispersion
  1080.       estimate output from the filter, in scrambled units.
  1081.  
  1082. 3.2.6.  Parameters
  1083.  
  1084.    Following is a list of parameters assumed for all implementations
  1085.    operating in the Internet system.  It is necessary to agree on the
  1086.    values for these parameters in order to avoid unnecessary network
  1087.    overheads and stable peer associations.
  1088.  
  1089.    Version Number (NTP.VERSION)
  1090.  
  1091.       This is the NTP version number, currently one (1).
  1092.  
  1093.    NTP Port (NTP.PORT)
  1094.  
  1095.       This is the port number (123) assigned by the Internet Number Czar
  1096.       to NTP.
  1097.  
  1098.    Minimum Polling Interval (NTP.MINPOLL)
  1099.  
  1100.       This is the minimum polling interval allowed by any peer of the
  1101.       Internet system, currently set to 6 (64 seconds).
  1102.  
  1103.    Maximum Polling Interval (NTP.MAXPOLL)
  1104.  
  1105.       This is the maximum polling interval allowed by any peer of the
  1106.       Internet system, currently set to 10 (1024 seconds).
  1107.  
  1108.    Maximum Dispersion (NTP.MAXDISP)
  1109.  
  1110.       This is the maximum dispersion assumed by the filter algorithms,
  1111.       currently set to 65535 milliseconds.
  1112.  
  1113.  
  1114.  
  1115.  
  1116. Mills                                                          [Page 20]
  1117.  
  1118. RFC 1059                 Network Time Protocol                 July 1988
  1119.  
  1120.  
  1121.    Reachability Register Size (PEER.WINDOW)
  1122.  
  1123.       This is the size of the Reachability Register (peer.reach),
  1124.       currently set to eight (8) bits.
  1125.  
  1126.    Shift Register Size (PEER.SHIFT)
  1127.  
  1128.       When the filter and selection algorithms suggested in Section 4
  1129.       are used, this is the size of the Clock Filter (peer.filter) shift
  1130.       register, in bits.  For crystal-stabilized oscillators a value of
  1131.       eight (8) is suggested, while for mains-frequency oscillators a
  1132.       value of four (4) is suggested.  Additional considerations are
  1133.       given in Section 5.
  1134.  
  1135.    Dispersion Threshold (PEER.THRESHOLD)
  1136.  
  1137.       When the filter and selection algorithms suggested in Section 4
  1138.       are used, this is the threshold used to discard noisy data.  While
  1139.       a value of 500 milliseconds is suggested, the value may be changed
  1140.       to suit local conditions on particular peer paths.
  1141.  
  1142.    Filter Weight (PEER.FILTER)
  1143.  
  1144.       When the filter algorithm suggested in Section 4 is used, this is
  1145.       the filter weight used to discard noisy data.  While a value of
  1146.       0.5 is suggested, the value may be changed to suit local
  1147.       conditions on particular peer paths.
  1148.  
  1149.    Select Weight (PEER.SELECT)
  1150.  
  1151.       When the selection algorithm suggested in Section 4 is used, this
  1152.       is the select weight used to discard outlyers.  data.  While a
  1153.       value of 0.75 is suggested, the value may be changed to suit local
  1154.       conditions on particular peer paths.
  1155.  
  1156. 3.3.  Modes of Operation
  1157.  
  1158.    An NTP host can operate in three modes:  client, server and
  1159.    symmetric.  The mode of operation is determined by whether the source
  1160.    port (peer.srcport) or destination port (peer.dstport) peer variables
  1161.    contain the assigned NTP service port number NTP.PORT (123) as shown
  1162.    in the following table.
  1163.  
  1164.  
  1165.  
  1166.  
  1167.  
  1168.  
  1169.  
  1170.  
  1171.  
  1172. Mills                                                          [Page 21]
  1173.  
  1174. RFC 1059                 Network Time Protocol                 July 1988
  1175.  
  1176.  
  1177.            peer.srcport    peer.dstport    Mode
  1178.            -------------------------------------------
  1179.            not NTP.PORT    not NTP.PORT    not possible
  1180.            not NTP.PORT    NTP.PORT        server
  1181.            NTP.PORT        not NTP.PORT    client
  1182.            NTP.PORT        NTP.PORT        symmetric
  1183.  
  1184.    A host operating in client mode occasionally sends an NTP message to
  1185.    a host operating in server mode.  The server responds by simply
  1186.    interchanging addresses and ports, filling in the required
  1187.    information and returning the message to the client.  Servers then
  1188.    need retain no state information between client requests.  Clients
  1189.    are free to manage the intervals between sending NTP messages to suit
  1190.    local conditions.
  1191.  
  1192.    In symmetric mode the client/server distinction disappears.  Each
  1193.    host maintains a table with as many entries as active peers.  Each
  1194.    entry includes a code uniquely identifying the peer (e.g.,  Internet
  1195.    address and port), together with status information and a copy of the
  1196.    timestamps last received.  A host operating in symmetric mode
  1197.    periodically sends NTP messages to each peer including the latest
  1198.    copy of the timestamps.  The intervals between sending NTP messages
  1199.    are managed jointly by the host and each peer using the polling
  1200.    variables peer.ppoll and peer.hpoll.
  1201.  
  1202.    When a pair of peers operating in symmetric mode exchange NTP
  1203.    messages and each determines that the other is reachable, an
  1204.    association is formed.  One or both peers must be in active state;
  1205.    that is, sending messages to the other regardless of reachability
  1206.    status.  A peer not in active state is in passive state.  If a peer
  1207.    operating in passive state discovers that the other peer is no longer
  1208.    reachable, it ceases sending messages and reclaims the storage and
  1209.    timer resources used by the association.  A peer operating in client
  1210.    mode is always in active state, while a peer operating in server mode
  1211.    is always in passive state.
  1212.  
  1213. 3.4.  Event Processing
  1214.  
  1215.    The significant events of interest in NTP occur upon expiration of
  1216.    the peer timer, one of which is dedicated to each peer operating in
  1217.    symmetric or client modes, and upon arrival of an NTP message from
  1218.    the various peers.  An event can also occur as the result of an
  1219.    operator command or detected system fault, such as a primary clock
  1220.    failure.  This section describes the procedures invoked when these
  1221.    events occur.
  1222.  
  1223.  
  1224.  
  1225.  
  1226.  
  1227.  
  1228. Mills                                                          [Page 22]
  1229.  
  1230. RFC 1059                 Network Time Protocol                 July 1988
  1231.  
  1232.  
  1233. 3.4.1.  Timeout Procedure
  1234.  
  1235.    The timeout procedure is called in client and symmetric modes when
  1236.    the peer timer (peer.timer) reaches the value of the timer threshold
  1237.    (peer.threshold) variable.  First, the reachability register
  1238.    (peer.reach) is shifted one position to the left and a zero replaces
  1239.    the vacated bit.  Then an NTP message is constructed and sent to the
  1240.    peer.  If operating in active state or in passive state and
  1241.    peer.reach is nonzero (reachable), the peer.timer is reinitialized
  1242.    (resumes counting from zero) and the value of peer.threshold is set
  1243.    to:
  1244.  
  1245.            peer.threshold <- max( min( peer.ppoll, peer.hpoll,
  1246.                            NTP.MAXPOLL), NTP.MINPOLL) .
  1247.  
  1248.    If operating in active state and peer.reach is zero (unreachable),
  1249.    the peer variables are updated as follows:
  1250.  
  1251.                    peer.hpoll <- NTP.MINPOLL
  1252.                    peer.disp <- NTP.MAXDISP
  1253.                    peer.filter <- 0 (cleared)
  1254.                    peer.org <- 0
  1255.                    peer.rec <- 0
  1256.  
  1257.    Then the clock selection algorithm is called, which may result in a
  1258.    new clock source (sys.peer).  In other cases the protocol ceases
  1259.    operation and the storage and timer resources are reclaimed for
  1260.    subsequent use.
  1261.  
  1262.    An NTP message is constructed as follows (see Appendices A and B for
  1263.    formats).  First, the IP and UDP packet variables are copied from the
  1264.    peer variables (note the interchange of source and destination
  1265.    addresses and ports):
  1266.  
  1267.            pkt.srcadr <- peer.dstadr       pkt.srcport <- peer.dstport
  1268.            pkt.dstadr <- peer.srcadr       pkt.dstport <- peer.srcport
  1269.  
  1270.    Next, the NTP packet variables are copied (rescaled as necessary)
  1271.    from the system and peer variables:
  1272.  
  1273.            pkt.leap <- sys.leap            pkt.distance <- sys.distance
  1274.            pkt.version <- NTP.VERSION      pkt.drift <- sys.drift
  1275.            pkt.stratum <- sys.stratum      pkt.refid <- sys.refid
  1276.            pkt.poll <- peer.hpoll          pkt.reftime <- sys.reftime
  1277.            pkt.precision <- sys.precision
  1278.  
  1279.    Finally, the NTP packet timestamp variables are copied, depending on
  1280.    whether the peer is operating in symmetric mode and reachable, in
  1281.  
  1282.  
  1283.  
  1284. Mills                                                          [Page 23]
  1285.  
  1286. RFC 1059                 Network Time Protocol                 July 1988
  1287.  
  1288.  
  1289.    symmetric mode and not reachable (but active) or in client mode:
  1290.  
  1291.    Symmetric Reachable     Symmetric Active        Client
  1292.    - -------------------     -------------------     -------------------
  1293.    pkt.org <- peer.org     pkt.org <- 0            pkt.org <- sys.clock
  1294.    pkt.rec <- peer.rec     pkt.rec <- 0            pkt.rec <- sys.clock
  1295.    pkt.xmt <- sys.clock    pkt.xmt <- sys.clock    pkt.xmt <- sys.clock
  1296.  
  1297.    Note that the order of copying should be designed so that the time to
  1298.    perform the copy operations themselves does not degrade the
  1299.    measurement accuracy, which implies that the sys.clock values should
  1300.    be copied last.  The reason for the choice of zeros to fill the
  1301.    pkt.org and pkt.rec packet variables in the symmetric unreachable
  1302.    case is to avoid the use of old data after a possibly extensive
  1303.    period of unreachability.  The reason for the choice of sys.clock to
  1304.    fill these variables in the client case is that, if for some reason
  1305.    the NTP message is returned by the recipient unaltered, as when
  1306.    testing with an Internet-echo server, this convention still allows at
  1307.    least the roundtrip time to be accurately determined without special
  1308.    handling.
  1309.  
  1310. 3.4.2.  Receive Procedure
  1311.  
  1312.    The receive procedure is executed upon arrival of an NTP message.  If
  1313.    the version number of the message (pkt.version) does not match the
  1314.    current version number (NTP.VERSION), the message is discarded;
  1315.    however, exceptions may be advised on a case-by-case basis at times
  1316.    when the version number is changed.
  1317.  
  1318.    If the clock of the sender is unsynchronized (pkt.leap = 11), or the
  1319.    receiver is in server mode or the receiver is in symmetric mode and
  1320.    the stratum of the sender is greater than the stratum of the receiver
  1321.    (pkt.stratum > sys.stratum), the message is simply returned to the
  1322.    sender along with the timestamps.  In this case the addresses and
  1323.    ports are interchanged in the IP and UDP headers:
  1324.  
  1325.         pkt.srcadr <-> pkt.dstadr       pkt.srcport <-> pkt.dstport
  1326.  
  1327.    The following packet variables are updated from the system variables:
  1328.  
  1329.         pkt.leap <- sys.leap            pkt.distance <- sys.distance
  1330.         pkt.version <- NTP.VERSION      pkt.drift <- sys.drift
  1331.         pkt.stratum <- sys.stratum      pkt.refid <- sys.refid
  1332.         pkt.precision <- sys.precision  pkt.reftime <- sys.reftime
  1333.  
  1334.    Note that the pkt.poll packet variable is unchanged.  The timestamps
  1335.    are updated in the order shown:
  1336.  
  1337.  
  1338.  
  1339.  
  1340. Mills                                                          [Page 24]
  1341.  
  1342. RFC 1059                 Network Time Protocol                 July 1988
  1343.  
  1344.  
  1345.                         pkt.org <- pkt.xmt
  1346.                         pkt.rec <- sys.clock
  1347.                         pkt.xmt <- sys.clock
  1348.  
  1349.    Finally, the message is forwarded to the sender and the server
  1350.    receive procedure terminated at this point.
  1351.  
  1352.    If the above is not the case, the source and destination Internet
  1353.    addresses and ports in the IP and UDP headers are matched to the
  1354.    correct peer.  If there is a match, processing continues at the next
  1355.    step below.  If there is no match and symmetric mode is not indicated
  1356.    (either pkt.srcport or pkt.dstport not equal to NTP.PORT), the
  1357.    message must be a reply to a previously sent message from a client
  1358.    which is no longer in operation.  In this case the message is dropped
  1359.    and the receive procedure terminated at this point.
  1360.  
  1361.    If there is no match and symmetric mode is indicated, (both
  1362.    pkt.srcport and pkt.dstport equal to NTP.PORT), an implementation-
  1363.    specific instantiation procedure is called to create and initialize a
  1364.    new set of peer variables and start the peer timer.  The following
  1365.    peer variables are set from the IP and UDP headers:
  1366.  
  1367.            peer.srcadr <- pkt.srcadr       peer.srcport <- pkt.srcport
  1368.            peer.dstadr <- pkt.dstadr       peer.dstport <- pkt.dstport
  1369.  
  1370.  
  1371.    The following peer variables are initialized:
  1372.  
  1373.                    peer.state <- symmetric (passive)
  1374.                    peer.timer <- 0 (enabled)
  1375.                    peer.hpoll <- NTP.MINPOLL
  1376.                    peer.disp <- NTP.MAXDISP
  1377.  
  1378.    The remaining peer variables are undefined and set to zero.
  1379.  
  1380.    Assuming that instantiation is complete and that match occurs, the
  1381.    least significant bit of the reachability register (peer.reach) is
  1382.    set, indicating the peer is now reachable.  The following peer
  1383.    variables are copied (rescaled as necessary) from the NTP packet
  1384.    variables and system variables:
  1385.  
  1386.  
  1387.  
  1388.  
  1389.  
  1390.  
  1391.  
  1392.  
  1393.  
  1394.  
  1395.  
  1396. Mills                                                          [Page 25]
  1397.  
  1398. RFC 1059                 Network Time Protocol                 July 1988
  1399.  
  1400.  
  1401.            peer.leap <- pkt.leap           peer.distance <- pkt.distance
  1402.            peer.stratum <- pkt.stratum     peer.drift <- pkt.drift
  1403.            peer.ppoll <- pkt.poll          peer.refid <- pkt.refid
  1404.            peer.precision <- pkt.precision peer.reftime <- pkt.reftime
  1405.            peer.org <- pkt.xmt             peer.rec <- sys.clock
  1406.            peer.threshold <- max( min( peer.ppoll, peer.hpoll,
  1407.                            NTP.MAXPOLL), NTP.MINPOLL)
  1408.  
  1409.    If either or both the pkt.org or pkt.rec packet variables are zero,
  1410.    the sender did not have reliable values for them, so the receive
  1411.    procedure is terminated at this point.  If both of these variables
  1412.    are nonzero, the roundtrip delay and clock offset relative to the
  1413.    peer are calculated as follows.  Number the times of sending and
  1414.    receiving NTP messages as shown in Figure 3.1 and let i be an even
  1415.    integer.  Then t(i-3), t(i-2) and t(i-1) and t(i) are the contents of
  1416.    the pkt.org, pkt.rec, pkt.xmt and peer.rec variables respectively.
  1417.  
  1418.                         |                    |
  1419.                    t(1) |------------------->| t(2)
  1420.                         |                    |
  1421.                    t(4) |<-------------------| t(3)
  1422.                         |                    |
  1423.                    t(5) |------------------->| t(6)
  1424.                         |                    |
  1425.                    t(8) |<-------------------| t(7)
  1426.                         |                    |
  1427.                                  ...
  1428.                 Figure 3.1. Calculating Delay and Offset
  1429.  
  1430.    The roundtrip delay d and clock offset c of the receiving peer
  1431.    relative to the sending peer is:
  1432.  
  1433.                    d = (t(i) - t(i-3)) - (t(i-1) - t(i-2))
  1434.                 c = [(t(i-2) - t(i-3)) + (t(i-1) - t(i))]/2 .
  1435.  
  1436.    This method amounts to a continuously sampled, returnable-time
  1437.    system, which is used in some digital telephone networks.  Among the
  1438.    advantages are that the order and timing of the messages is
  1439.    unimportant and that reliable delivery is not required.  Obviously,
  1440.    the accuracies achievable depend upon the statistical properties of
  1441.    the outbound and inbound net paths.  Further analysis and
  1442.    experimental results bearing on this issue can be found in
  1443.    Appendix D.
  1444.  
  1445.    The c and d values are then input to the clock filter algorithm to
  1446.    produce the delay estimate (peer.delay) and offset estimate
  1447.    (peer.offset) for the peer involved.  If d becomes nonpositive due to
  1448.    low delays, long polling intervals and high drift rates, it should be
  1449.  
  1450.  
  1451.  
  1452. Mills                                                          [Page 26]
  1453.  
  1454. RFC 1059                 Network Time Protocol                 July 1988
  1455.  
  1456.  
  1457.    considered invalid;  however, even under these conditions it may
  1458.    still be useful to update the local clock and reduce the drift rate
  1459.    to the point that d becomes positive again.  Specification of the
  1460.    clock filter algorithm is not an integral part of the NTP
  1461.    specification;  however, one found to work well in the Internet
  1462.    environment is described in Section 4.
  1463.  
  1464.    When a primary clock is connected to the host, it is convenient to
  1465.    incorporate its information into the data base as if the clock were
  1466.    represented by an ordinary peer.  The clocks are usually polled once
  1467.    or twice a minute and the returned timecheck used to produce a new
  1468.    update for the logical clock.  The update procedure is then called
  1469.    with the following assumed peer variables:
  1470.  
  1471.                    peer.offset <- timecheck - sys.clock
  1472.                    peer.delay <- as determined
  1473.                    peer.dispersion <- 0
  1474.                    peer.leap <- selected by operator, ordinarily 00
  1475.                    peer.stratum <- 0
  1476.                    peer.distance <- 0
  1477.                    peer.refid <- ASCII identifier
  1478.                    peer.reftime <- timecheck
  1479.  
  1480.    In this case the peer.delay and peer.refid can be constants
  1481.    reflecting the type and accuracy of the clock.  By convention, the
  1482.    value for peer.delay is ten times the expected mean error of the
  1483.    clock, for instance, 10 milliseconds for a WWVB clock and 1000
  1484.    milliseconds for a less accurate WWV clock, but with a floor of 100
  1485.    milliseconds.  Other peer variables such as the peer timer and
  1486.    reachability register can be used to control the polling interval and
  1487.    to confirm the clock is operating correctly.  In this way the clock
  1488.    filter and selection algorithms operate in the usual way and can be
  1489.    used to mitigate the clock itself, should it appear to be operating
  1490.    correctly, yet deliver bogus time.
  1491.  
  1492. 3.4.3.  Update Procedure
  1493.  
  1494.    The update procedure is called when a new delay/offset estimate is
  1495.    available.  First, the clock selection algorithm determines the best
  1496.    peer on the basis of estimated accuracy and reliability, which may
  1497.    result in a new clock source (sys.peer).  If sys.peer points to the
  1498.    peer data structure with the just-updated estimates, the state
  1499.    variables of that peer are used to update the system state variables
  1500.  
  1501.  
  1502.  
  1503.  
  1504.  
  1505.  
  1506.  
  1507.  
  1508. Mills                                                          [Page 27]
  1509.  
  1510. RFC 1059                 Network Time Protocol                 July 1988
  1511.  
  1512.  
  1513.    as follows:
  1514.  
  1515.                    sys.leap <- peer.leap
  1516.                    sys.stratum <- peer.stratum + 1
  1517.                    sys.distance <- peer.distance + peer.delay
  1518.                    sys.refid <- peer.srcadr
  1519.                    sys.reftime <- peer.rec
  1520.  
  1521.    Finally, the logical clock procedure is called with peer.offset as
  1522.    argument to update the logical clock (sys.clock) and recompute the
  1523.    estimated drift rate (sys.drift).  It may happen that the logical
  1524.    clock may be reset, rather than slewed to its final value.  In this
  1525.    case the peer variables of all reachable peers are are updated as
  1526.    follows:
  1527.  
  1528.                    peer.hpoll <- NTP.MINPOLL
  1529.                    peer.disp <- NTP.MAXDISP
  1530.                    peer.filter <- 0 (cleared)
  1531.                    peer.org <- 0
  1532.                    peer.rec <- 0
  1533.  
  1534.    and the clock selection algorithm is called again, which results in a
  1535.    null clock source (sys.peer = 0).  A new selection will occur when
  1536.    the filters fill up again and the dispersion settles down.
  1537.  
  1538.    Specification of the clock selection algorithm and logical clock
  1539.    procedure is not an integral part of the NTP specification.  A clock
  1540.    selection algorithm found to work well in the Internet environment is
  1541.    described in Section 4, while a logical clock procedure is described
  1542.    in Section 5.  The clock selection algorithm described in Section 4
  1543.    usually picks the server at the highest stratum and minimum delay
  1544.    among all those available, unless that server appears to be a
  1545.    falseticker.  The result is that the algorithms all work to build a
  1546.    minimum-weight spanning tree relative to the primary servers and thus
  1547.    a hierarchical master-slave system similar to those used by some
  1548.    digital telephone networks.
  1549.  
  1550.  
  1551.  
  1552.  
  1553.  
  1554.  
  1555.  
  1556.  
  1557.  
  1558.  
  1559.  
  1560.  
  1561.  
  1562.  
  1563.  
  1564. Mills                                                          [Page 28]
  1565.  
  1566. RFC 1059                 Network Time Protocol                 July 1988
  1567.  
  1568.  
  1569. 3.4.4.  Initialization Procedures
  1570.  
  1571.    Upon reboot the NTP host initializes all system variables as follows:
  1572.  
  1573.                    sys.clock <- best available estimate
  1574.                    sys.leap <- 11 (unsynchronized)
  1575.                    sys.stratum <- 0 (undefined)
  1576.                    sys.precision <- as required
  1577.                    sys.distance <- 0 (undefined)
  1578.                    sys.drift <- as determined
  1579.                    sys.refid <- 0 (undefined)
  1580.                    sys.reftime <- 0 (undefined)
  1581.  
  1582.    The logical clock sys.clock is presumably undefined at reboot;
  1583.    however, in some designs such as the Fuzzball an estimate is
  1584.    available from the reboot environment.  The sys.precision variable is
  1585.    determined by the intrinsic architecture of the local hardware clock.
  1586.    The sys.drift variable is determined as a side effect of subsequent
  1587.    logical clock updates, from whatever source.
  1588.  
  1589.    Next, an implementation-specific instantiation procedure is called
  1590.    repeatedly to establish the set of client peers or symmetric (active)
  1591.    peers which will actively probe other servers during regular
  1592.    operation.  The mode and addresses of these peers is determined using
  1593.    information read during the reboot procedure or as the result of
  1594.    operator commands.
  1595.  
  1596. 4.  Filtering Algorithms
  1597.  
  1598.    A very important factor affecting the accuracy and reliability of
  1599.    time distribution is the complex of algorithms used to deglitch and
  1600.    smooth the offset estimates and to cast out outlyers due to failure
  1601.    of the primary reference sources or propagation media.  The
  1602.    algorithms suggested in this section were developed and refined over
  1603.    several years of operation in the Internet under widely varying net
  1604.    configurations and utilizations.  While these algorithms are believed
  1605.    the best available at the present time, they are not an integral part
  1606.    of the NTP specification.
  1607.  
  1608.    There are two algorithms described in the following, the clock filter
  1609.    algorithm, which is used to select the best offset samples from a
  1610.    given clock, and the clock selection algorithm, which is used to
  1611.    select the best clock among a hierarchical set of clocks.
  1612.  
  1613. 4.1.  Clock Filter Algorithm
  1614.  
  1615.    The clock filter algorithm is executed upon arrival of each NTP
  1616.    message that results in new delay/offset sample pairs.  New sample
  1617.  
  1618.  
  1619.  
  1620. Mills                                                          [Page 29]
  1621.  
  1622. RFC 1059                 Network Time Protocol                 July 1988
  1623.  
  1624.  
  1625.    pairs are shifted into the filter register (peer.filter) from the
  1626.    left end, causing first zeros then old sample pairs to shift off the
  1627.    right end.  Then those sample pairs in peer.filter with nonzero delay
  1628.    are inserted on a temporary list and sorted in order of increasing
  1629.    delay.  The delay estimate (peer.delay) and offset estimate
  1630.    (peer.offset) are chosen as the delay/offset values corresponding to
  1631.    the minimum-delay sample.  In case of ties an arbitrary choice is
  1632.    made.
  1633.  
  1634.    The dispersion estimate (peer.dispersion) is then computed as the
  1635.    weighted sum of the offsets in the list.  Assume the list has
  1636.    PEER.SHIFT entries, the first m of which contain valid samples in
  1637.    order of increasing delay.  If X(i) (0 =< i < PEER.SHIFT) is the
  1638.    offset of the ith sample, then,
  1639.  
  1640.            d(i) = |X(i) - X(0)|    if i < m and |X(i) - X(0)| < 2^15
  1641.            d(i) = 2^15 - 1         otherwise
  1642.  
  1643.                    peer.dispersion = Sum(d(i)*w^i) ,
  1644.                            (0 =< i < PEER.SHIFT)
  1645.  
  1646.    where w < 1 is a weighting factor experimentally adjusted to match
  1647.    typical offset distributions.  The peer.dispersion variable is
  1648.    intended for use as a quality indicator, with increasing values
  1649.    associated with decreasing quality.  The intent is that samples with
  1650.    a peer.dispersion exceeding a configuration threshold will not be
  1651.    used in subsequent processing.  The prototype implementation uses a
  1652.    weighting factor w = 0.5, also called PEER.FILTER, and a threshold
  1653.    PEER.THRESHOLD of 500 ms, which insures that all stages of
  1654.    peer.filter are filled and contain offsets within a few seconds of
  1655.    each other.
  1656.  
  1657. 4.2.  Clock Selection Algorithm
  1658.  
  1659.    The clock selection algorithm uses the values of peer.delay,
  1660.    peer.offset and peer.dispersion calculated by the clock filter
  1661.    algorithm and is called when these values change or when the
  1662.    reachability status changes.  It constructs a list of candidate
  1663.    estimates according to a set of criteria designed to maximize
  1664.    accuracy and reliability, then sorts the list in order of estimated
  1665.    precision.  Finally, it repeatedly casts out outlyers on the basis of
  1666.    dispersion until only a single candidate is left.
  1667.  
  1668.    The selection process operates on each peer in turn and inspects the
  1669.    various data captured from the last received NTP message header, as
  1670.    well as the latest clock filter estimates.  It selects only those
  1671.    peers for which the following criteria are satisfied:
  1672.  
  1673.  
  1674.  
  1675.  
  1676. Mills                                                          [Page 30]
  1677.  
  1678. RFC 1059                 Network Time Protocol                 July 1988
  1679.  
  1680.  
  1681.    1.  The peer must be reachable and operating in client or symmetric
  1682.        modes.
  1683.  
  1684.    2.  The peer logical clock must be synchronized, as indicated by the
  1685.        Leap Indicator bits being other than 11.
  1686.  
  1687.    3.  If the peer is operating at stratum two or greater, it must not
  1688.        be synchronized to this host, which means its reference clock
  1689.        identifier (peer.refid) must not match the Internet address of
  1690.        this host.  This is analogous to the split-horizon rule used in
  1691.        some variants of the Bellman-Ford routing algorithm.
  1692.  
  1693.    4.  The sum of the peer synchronizing distance (peer.distance) plus
  1694.        peer.delay must be less than 2^13 (8192) milliseconds.  Also, the
  1695.        peer stratum (peer.stratum) must be less than eight and
  1696.        peer.dispersion must be less than a configured threshold
  1697.        PEER.THRESHOLD (currently 500 ms).  These range checks were
  1698.        established through experience with the prototype implementation,
  1699.        but may be changed in future.
  1700.  
  1701.    For each peer which satisfies the above criteria, a sixteen-bit
  1702.    keyword is constructed, with the low-order thirteen bits the sum of
  1703.    peer.distance plus peer.delay and the high-order three bits the
  1704.    peer.stratum reduced by one and truncated to three bits (thus mapping
  1705.    zero to seven).  The keyword together with a pointer to the peer data
  1706.    structure are inserted according to increasing keyword values and
  1707.    truncated at a maximum of eight entries.  The resulting list
  1708.    represents the order in which peers should be chosen according to the
  1709.    estimated precision of measurement.  If no keywords are found, the
  1710.    clock source variable (sys.peer) is set to zero and the algorithm
  1711.    terminates.
  1712.  
  1713.    The final procedure is designed to detect falsetickers or other
  1714.    conditions which might result in gross errors.  Let m be the number
  1715.    of samples remaining in the list.  For each i (0 =< i < m) compute
  1716.    the dispersion d(i) of the list relative to i:
  1717.  
  1718.                    d(i) = Sum(|X(j) - X(i)|*w^j) ,
  1719.                        (0 =< j < m)
  1720.  
  1721.    where w < 1 is a weighting factor experimentally adjusted for the
  1722.    desired characteristic (see below).  Then cast out the entry with
  1723.    maximum d(i) or, in case of ties, the maximum i, and repeat the
  1724.    procedure.  When only a single entry remains in the list, sys.peer is
  1725.    set as its peer data structure pointer and the peer.hpoll variable in
  1726.    that structure is set to NTP.MINPOLL as required by the logical clock
  1727.    mechanism described in Section 5.
  1728.  
  1729.  
  1730.  
  1731.  
  1732. Mills                                                          [Page 31]
  1733.  
  1734. RFC 1059                 Network Time Protocol                 July 1988
  1735.  
  1736.  
  1737.    This procedure is designed to favor those peers near the head of the
  1738.    list, which are at the highest stratum and lowest delay and
  1739.    presumably can provide the most precise time.  With proper selection
  1740.    of weighting factor w, also called PEER.SELECT, entries will be
  1741.    trimmed from the tail of the list, unless a few outlyers disagree
  1742.    significantly with respect to the remaining entries, in which case
  1743.    the outlyers are discarded first.
  1744.  
  1745.    In order to see how this procedure works to select outlyers, consider
  1746.    the case of three entries and assume that one or more of the offsets
  1747.    are clustered about zero and others are clustered about one.  For w =
  1748.    0.75 as used in the prototype implementations and multiplying by 16
  1749.    for convenience, the first entry has weight w^0 = 16, the second w^1
  1750.    = 12 and the third w^2 = 9.  Table X shows for all combinations of
  1751.    peer offsets the calculated dispersion about each of the three
  1752.    entries, along with the results of the procedure.
  1753.  
  1754.       Peer 0    1    2         Dispersion          Cast    Result
  1755.     Weight 16   12   9     0       1       2       Out
  1756.            ------------------------------------------------------
  1757.            0    0    0     0       0       0       2       0    0
  1758.            0    0    1     9       9       28      2       0    0
  1759.            0    1    0     12      25      12      1       0    0
  1760.            0    1    1     21      16      16      0       1    1
  1761.            1    0    0     21      16      16      0       0    0
  1762.            1    0    1     12      25      12      1       1    1
  1763.            1    1    0     9       9       28      2       1    1
  1764.            1    1    1     0       0       0       2       1    1
  1765.  
  1766.                   Table 4.1. Outlyer Selection Procedure
  1767.  
  1768.    In the four cases where peer 0 and peer 1 disagree, the outcome is
  1769.    determined by peer 2.  Similar outcomes occur in the case of four
  1770.    peers.  While these outcomes depend on judicious choice of w, the
  1771.    behavior of the algorithm is substantially the same for values of w
  1772.    between 0.5 and 1.0.
  1773.  
  1774. 4.3.  Variable-Rate Polling
  1775.  
  1776.    As NTP service matures in the Internet, the resulting network traffic
  1777.    can become burdensome, especially in the primary service net.  In
  1778.    this expectation, it is useful to explore variable-rate polling, in
  1779.    which the intervals between NTP messages can be adjusted to fit
  1780.    prevailing network conditions of delay dispersion and loss rate.  The
  1781.    prototype NTP implementation uses this technique to reduce the
  1782.    network overheads to one-sixteenth the maximum rate, depending on
  1783.    observed dispersion and loss.
  1784.  
  1785.  
  1786.  
  1787.  
  1788. Mills                                                          [Page 32]
  1789.  
  1790. RFC 1059                 Network Time Protocol                 July 1988
  1791.  
  1792.  
  1793.    The prototype implementation adjusts the polling interval peer.hpoll
  1794.    in response to the reachability register (peer.reach) variable along
  1795.    with the dispersion (peer.dispersion) variable.  So long as the clock
  1796.    source variable (sys.peer) does not point to the peer data structure,
  1797.    peer.reach is nonzero (reachable) and peer.dispersion is less than
  1798.    the PEER.THRESHOLD parameter, the value of peer.hpoll is increased by
  1799.    one for each call on the update procedure, subject to a maximum of
  1800.    NTP.MAXPOLL.  Following the timeout procedure, if peer.reach
  1801.    indicates messages have not been received for the preceding two
  1802.    polling intervals (low-order two bits are zero), the value of
  1803.    peer.hpoll is decreased by one, subject to a minimum of NTP.MINPOLL.
  1804.    If peer.reach becomes zero (unreachable), the value of peer.hpoll is
  1805.    set to NTP.MINPOLL.
  1806.  
  1807.    The result of the above mechanism is that the polling intervals for
  1808.    peers not selected for synchronization and in symmetric mode creep
  1809.    upwards once the filter register (peer.filter) has filled and the
  1810.    peer.dispersion has settled down, but decrease again in case
  1811.    peer.dispersion increases or the loss rate increases or the peer
  1812.    becomes unreachable.
  1813.  
  1814. 5.  Logical Clocks
  1815.  
  1816.    In order to implement a logical clock, the host must be equipped with
  1817.    a hardware clock consisting of an oscillator and interface and
  1818.    capable of the required precision and stability.  The logical clock
  1819.    is adjusted by means of periodic offset corrections computed by NTP
  1820.    or some other time-synchronization protocol such as Hellospeak [15]
  1821.    or the Unix 4.3bsd TSP [20].  Following is a description of the
  1822.    Fuzzball logical clock, which includes provisions for precise time
  1823.    and frequency adjustment and can maintain time to within a
  1824.    millisecond and frequency to within a day per millisecond.
  1825.  
  1826.    The logical clock is implemented using a 48-bit Clock Register, which
  1827.    increments at 1000-Hz (at the decimal point), a 32-bit Clock-Adjust
  1828.    Register, which is used to slew the Clock Register in response to
  1829.    offset corrections, and a Drift-Compensation Register, which is used
  1830.    to trim the oscillator frequency.  In some interface designs such as
  1831.    the DEC KWV11, an additional hardware register, the Counter Register,
  1832.    is used as an auxiliary counter.  The configuration and decimal point
  1833.    of these registers are shown in Figure 5.1.
  1834.  
  1835.  
  1836.  
  1837.  
  1838.  
  1839.  
  1840.  
  1841.  
  1842.  
  1843.  
  1844. Mills                                                          [Page 33]
  1845.  
  1846. RFC 1059                 Network Time Protocol                 July 1988
  1847.  
  1848.  
  1849.            Clock Register
  1850.  
  1851.            0               16               32
  1852.            +---------------+---------------+---------------+
  1853.            |               |               |               |
  1854.            +---------------+---------------+---------------+
  1855.                                            A
  1856.                                      decimal point
  1857.  
  1858.            Clock-Adjust Register
  1859.  
  1860.                            0               16
  1861.                            +---------------+---------------+
  1862.                            |               |               |
  1863.                            +---------------+---------------+
  1864.                                            A
  1865.                                      decimal point
  1866.  
  1867.            Drift-Compensation Register
  1868.  
  1869.                            0               16
  1870.                            +---------------+
  1871.                            |               |
  1872.                            +---------------+
  1873.                                            A
  1874.                                      decimal point
  1875.  
  1876.            Counter Register
  1877.  
  1878.                            0               16
  1879.                            +---------------+
  1880.                            |               |
  1881.                            +---------------+
  1882.                                            A
  1883.                                      decimal point
  1884.  
  1885.                         Figure 5.1. Clock Registers
  1886.  
  1887.    The Clock Register, Clock-Adjust Register and Drift-Compensation
  1888.    Register are implemented in memory.  In typical clock interface
  1889.    designs such as the DEC KWV11, the Counter Register is implemented as
  1890.    a buffered counter driven by a crystal oscillator.  A counter
  1891.    overflow is signalled by an interrupt, which results in an increment
  1892.    of the Clock Register at bit 15 and the propagation of carries as
  1893.    required.  The time of day is determined by reading the Counter
  1894.    Register, which does not disturb the counting process, and adding its
  1895.    value to that of the Clock Register with decimal points aligned.
  1896.  
  1897.  
  1898.  
  1899.  
  1900. Mills                                                          [Page 34]
  1901.  
  1902. RFC 1059                 Network Time Protocol                 July 1988
  1903.  
  1904.  
  1905.    In other interface designs such as the LSI-11 event-line mechanism,
  1906.    each tick of the clock is signalled by an interrupt at intervals of
  1907.    16-2/3 or 20 ms, depending on interface and mains frequency.  When
  1908.    this occurs the appropriate increment in milliseconds, expressed to
  1909.    32 bits in precision, is added to the Clock Register with decimal
  1910.    points aligned.
  1911.  
  1912. 5.1.  Uniform Phase Adjustments
  1913.  
  1914.    Left uncorrected, the logical clock runs at the rate of its intrinsic
  1915.    oscillator.  A correction is introduced as a signed 32-bit integer in
  1916.    milliseconds, which is added to the Drift-Compensation Register and
  1917.    also replaces bits 0-15 of the Clock-Adjust Register, with bits 16-31
  1918.    set to zero.  At adjustment intervals of CLOCK.ADJ a correction
  1919.    consisting of two components is computed.  The first (phase)
  1920.    component consists of the Clock-Adjust Register shifted right
  1921.    CLOCK.PHASE bits, which is then subtracted from the Clock-Adjust
  1922.    Register.  The second (frequency) component consists of the Drift-
  1923.    Compensation Register shifted right CLOCK.FREQ bits.  The sum of the
  1924.    phase and frequency components is the correction, which is then added
  1925.    to the Clock Register.  Operation continues in this way until a new
  1926.    correction is introduced.
  1927.  
  1928.    Care is required in the implementation to insure monotonicity of the
  1929.    Clock Register and to preserve the highest precision while minimizing
  1930.    the propagation of roundoff errors.  This can be done by buffering
  1931.    the corrections and adding them to the increment at the time the
  1932.    Clock Register is next updated.  Monotonicity is insured with the
  1933.    parameters shown in Table 5.1, as long as the increment is at least 2
  1934.    ms.  This table shows the above parameters and others discussed below
  1935.    for both a crystal-stabilized oscillator and a mains-frequency
  1936.    oscillator.
  1937.  
  1938.    Parameter               Name            Crystal         Mains
  1939.    -------------------------------------------------------------------
  1940.    Update Interval         CLOCK.ADJ       4 sec           1 sec
  1941.    Phase Shift             CLOCK.PHASE     -8              -9
  1942.    Frequency Shift         CLOCK.FREQ      -16             -16
  1943.    Maximum Aperture        CLOCK.MAX       +-128 ms        +-256 ms
  1944.    Shift Register Size     PEER.SHIFT      8               4
  1945.    Host Poll Interval      peer.hpoll      NTP.MINPOLL     NTP.MINPOLL
  1946.                                             (64 sec)        (64 sec)
  1947.  
  1948.                         Table 5.1. Clock Parameters
  1949.  
  1950.    The above design constitutes a second-order phase-lock loop which
  1951.    adjusts the logical clock phase and frequency to compensate for the
  1952.    intrinsic oscillator jitter, wander and drift.  Simulation of a loop
  1953.  
  1954.  
  1955.  
  1956. Mills                                                          [Page 35]
  1957.  
  1958. RFC 1059                 Network Time Protocol                 July 1988
  1959.  
  1960.  
  1961.    with parameters chosen from Table 5.1 for a crystal-stabilized
  1962.    oscillator and the clock filter described in Section 4 results in the
  1963.    following transient response:  For a phase correction of 100 ms the
  1964.    loop reaches zero error in 34 minutes, overshoots 7 ms in 76 minutes
  1965.    and settles to less than 1 ms in about four hours.  The maximum
  1966.    frequency error is about 6 ppm at 40 minutes and returns to less than
  1967.    1 ppm in about eight hours.  For a frequency correction of 10 ppm the
  1968.    loop settles to within 1 ppm in about nine hours and to within 0.1
  1969.    ppm in about a day.  These characteristics are appropriate for
  1970.    typical computing equipment using board-mounted crystals without oven
  1971.    temperature control.
  1972.  
  1973.    In those cases where mains-frequency oscillators must be used, the
  1974.    loop parameters must be adapted for the relatively high jitter and
  1975.    wander characteristics of the national power grid, in which diurnal
  1976.    peak-to-peak phase excursions can exceed four seconds.  Simulation of
  1977.    a loop with parameters chosen from Table 5.1 for a mains-frequency
  1978.    oscillator and the clock filter described in Section 4 results in a
  1979.    transient response similar to the crystal-stabilized case, but with
  1980.    time constants only one-fourth those in that case.  When presented
  1981.    with actual phase-offset data for typical Summer days when the jitter
  1982.    and wander are the largest, the loop errors are in the order of a few
  1983.    tens of milliseconds, but not greater than 150 ms.
  1984.  
  1985.    The above simulations assume the clock filter algorithm operates to
  1986.    select the oldest sample in the shift register at each step;  that
  1987.    is, the filter operates as a delay line with delay equal to the
  1988.    polling interval times the number of stages.  This is a worst-case
  1989.    scenario, since the larger the overall delay the harder it is to
  1990.    maintain low loop errors together with good transient response.  The
  1991.    parameters in Table 5.1 were experimentally determined with this
  1992.    scenario and the constraint that the polling interval could not be
  1993.    reduced below 64 seconds.  With these parameters it is not possible
  1994.    to increase the polling interval above 64 seconds without significant
  1995.    increase in loop error or degradation of transient response.  Thus,
  1996.    when a clock is selected according to the algorithms of Section 4,
  1997.    the polling interval peer.hpoll is always set at NTP.MINPOLL.
  1998.  
  1999. 5.2.  Nonuniform Phase Adjustments
  2000.  
  2001.    When the magnitude of a correction exceeds a maximum aperture
  2002.    CLOCK.MAX, the possibility exists that the clock is so far out of
  2003.    synchronization with the reference source that the best action is an
  2004.    immediate and wholesale replacement of Clock Register contents,
  2005.    rather than a graduated slewing as described above.  In practice the
  2006.    necessity to do this is rare and occurs when the local host or
  2007.    reference source is rebooted, for example.  This is fortunate, since
  2008.    step changes in the clock can result in the clock apparently running
  2009.  
  2010.  
  2011.  
  2012. Mills                                                          [Page 36]
  2013.  
  2014. RFC 1059                 Network Time Protocol                 July 1988
  2015.  
  2016.  
  2017.    backward, as well as incorrect delay and offset measurements of the
  2018.    synchronization mechanism itself.
  2019.  
  2020.    Considerable experience with the Internet environment suggests the
  2021.    values of CLOCK.MAX tabulated in Table 5.1 as appropriate.  In
  2022.    practice, these values are exceeded with a single time-server source
  2023.    only under conditions of the most extreme congestion or when multiple
  2024.    failures of nodes or links have occured.  The most common case when
  2025.    the maximum is exceeded is when the time-server source is changed and
  2026.    the time indicated by the new and old sources exceeds the maximum due
  2027.    to systematic errors in the primary reference source or large
  2028.    differences in the synchronizing path delays.
  2029.  
  2030. 5.3.  Maintaining Date and Time
  2031.  
  2032.    Conversion from NTP format to the common date and time formats used
  2033.    by application programs is simplified if the internal local-clock
  2034.    format uses separate date and time registers.  The time register is
  2035.    designed to roll over at 24 hours, give or take a leap second as
  2036.    determined by the Leap Indicator bits, with its overflows
  2037.    (underflows) incrementing (decrementing) the date register.  The date
  2038.    and time registers then indicate the number of days and seconds since
  2039.    some previous reference time, but uncorrected for leap seconds.
  2040.  
  2041.    On the day prior to the insertion of a leap second the Leap Indicator
  2042.    bits are set at the primary servers, presumably by manual means.
  2043.    Subsequently, these bits show up at the local host and are passed to
  2044.    the logical clock procedure.  This causes the modulus of the time
  2045.    register, which is the length of the current day, to be increased or
  2046.    decreased by one second as appropriate.  On the day following
  2047.    insertion the bits are turned off at the primary servers.  While it
  2048.    is possible to turn the bits off automatically, the procedure
  2049.    suggested here insures that all clocks have rolled over and will not
  2050.    be reset incorrectly to the previous day as the result of possible
  2051.    corrections near the instant of rollover.
  2052.  
  2053. 5.4.  Estimating Errors
  2054.  
  2055.    After an NTP message is received and until the next one is received,
  2056.    the accuracy of the local clock can be expected to degrade somewhat.
  2057.    The magnitude of this degradation depends on the error at the last
  2058.    update time together with the drift of the local oscillator with
  2059.    respect to time.  It is possible to estimate both the error and drift
  2060.    rate from data collected during regular operation.  These data can be
  2061.    used to determine the rate at which NTP neighbors should exchange NTP
  2062.    messages and thus control net overheads.
  2063.  
  2064.    NTP messages include the local-clock precision of the sender, as well
  2065.  
  2066.  
  2067.  
  2068. Mills                                                          [Page 37]
  2069.  
  2070. RFC 1059                 Network Time Protocol                 July 1988
  2071.  
  2072.  
  2073.    as the reference time, estimated drift and a quantity called the
  2074.    synchronizing distance.  The precision of the local clock, together
  2075.    with its peer clocks, establishes the short-term jitter
  2076.    characteristics of the offset estimates.  The reference time and
  2077.    estimated drift of the sender provide an error estimate at the time
  2078.    the latest update was received.  The synchronizing distance provides
  2079.    an estimate of error relative to the primary reference source and is
  2080.    used by the filtering algorithms to improve the quality and
  2081.    reliability of the offset estimates.
  2082.  
  2083.    Estimates of error and drift rate are not essential for the correct
  2084.    functioning of the clock algorithms, but do improve the accuracy and
  2085.    adjustment with respect to net overheads.  The estimated error allows
  2086.    the recipient to compute the rate at which independent samples are
  2087.    required in order to maintain a specified estimated error.  The
  2088.    estimated drift rate allows the recipient to estimate the optimum
  2089.    polling interval.
  2090.  
  2091.    It is possible to compute the estimated drift rate of the local clock
  2092.    to a high degree of precision by simply adding the n offsets received
  2093.    during an interval T to an accumulator.  If X1 and X2 are the values
  2094.    of the accumulator at the beginning and end of T, then the estimated
  2095.    drift rate r is:
  2096.  
  2097.                                X2 - X1  n
  2098.                            r = ------- --- .
  2099.                                   n     T
  2100.  
  2101.    The intrinsic (uncorrected) drift rate of typical crystal oscillators
  2102.    under room-temperature conditions is in the order of from a few parts
  2103.    per million (ppm) to as much as 100 ppm, or up to a few seconds per
  2104.    day.  For most purposes the drift of a particular crystal oscillator
  2105.    is constant to within perhaps one ppm.  Assuming T can be estimated
  2106.    to within 100 ms, for example, it would take about a day of
  2107.    accumulation to estimate r to an uncertainty in the order of one ppm.
  2108.  
  2109.    Some idea of the estimated error of the local clock can be derived
  2110.    from the variance of the offsets about the mean per unit time.  This
  2111.    can be computed by adding the n offset squares received during T to
  2112.    an accumulator.  If Y1 and Y2 are the values of the accumulator at
  2113.    the beginning and end of T, then the estimated error s is:
  2114.  
  2115.                          Y2 - Y1   (X2 - X1)^2    n
  2116.                    s = ( ------- - ----------- ) --- .
  2117.                             n         n * n       T
  2118.  
  2119.    The quantities r and s have direct utility to the peer as noted
  2120.    above.  However, they also have indirect utility to the recipient of
  2121.  
  2122.  
  2123.  
  2124. Mills                                                          [Page 38]
  2125.  
  2126. RFC 1059                 Network Time Protocol                 July 1988
  2127.  
  2128.  
  2129.    an NTP message sent by that peer, since they can be used as weights
  2130.    in such algorithms as described in [22], as well as to improve the
  2131.    estimates during periods when offsets are not available.  It is most
  2132.    useful if the latest estimate of these quantities are available in
  2133.    each NTP message sent;  however, considerable latitude remains in the
  2134.    details of computation and storage.
  2135.  
  2136.    The above formulae for r and s imply equal weighting for offsets
  2137.    received throughout the accumulation interval T.  One way to do this
  2138.    is using a software shift register implemented as a circular buffer.
  2139.    A single pointer points to the active entry in the buffer and
  2140.    advances around one entry as each new offset is stored.  There are
  2141.    two accumulators, one for the offset and the other for its squares.
  2142.    When a new offset arrives, a quantity equal to the new offset minus
  2143.    the old (active) entry is added to the first accumulator and the
  2144.    square of this quantity is added to the second.  Finally, the offset
  2145.    is stored in the circular buffer.
  2146.  
  2147.    The size of the circular buffer depends on the accumulation interval
  2148.    T and the rate offsets are produced.  In many reachability and
  2149.    routing algorithms, such as GGP, EGP and local-net control
  2150.    algorithms, peers exchange messages on the order of once or twice a
  2151.    minute.  If NTP peers exchanged messages at a rate of one per minute
  2152.    and if T were one day, the circular buffer would have to be 1440
  2153.    words long;  however, a less costly design might aggregate the data
  2154.    in something like half-hour segments, which would reduce the length
  2155.    of the buffer to 48 words while not significantly affecting the
  2156.    quality of the data.
  2157.  
  2158.  
  2159.  
  2160.  
  2161.  
  2162.  
  2163.  
  2164.  
  2165.  
  2166.  
  2167.  
  2168.  
  2169.  
  2170.  
  2171.  
  2172.  
  2173.  
  2174.  
  2175.  
  2176.  
  2177.  
  2178.  
  2179.  
  2180. Mills                                                          [Page 39]
  2181.  
  2182. RFC 1059                 Network Time Protocol                 July 1988
  2183.  
  2184.  
  2185. 6.  References
  2186.  
  2187.    1.  Lamport, L., "Time, Clocks and the Ordering of Events in a
  2188.        Distributed System", Communications of the ACM, Vol. 21, No. 7,
  2189.        pgs.  558-565, July 1978.
  2190.  
  2191.    2.  "Time and Frequency Dissemination Services", NBS Special
  2192.        Publication No. 432, US Department of Commerce, 1979.
  2193.  
  2194.    3.  Lindsay, W., and A.  Kantak, "Network Synchronization of Random
  2195.        Signals", IEEE Trans. Comm., COM-28, No. 8, pgs. 1260-1266,
  2196.        August 1980.
  2197.  
  2198.    4.  Braun, W., "Short Term Frequency Effects in Networks of Coupled
  2199.        Oscillators", IEEE Trans. Comm., COM-28, No. 8, pgs. 1269-1275,
  2200.        August 1980.
  2201.  
  2202.    5.  Mitra, D., "Network Synchronization:  Analysis of a Hybrid of
  2203.        Master-Slave and Mutual Synchronization", IEEE Trans. Comm.
  2204.        COM-28, No. 8, pgs. 1245-1259, August 1980.
  2205.  
  2206.    6.  Postel, J., "User Datagram Protocol", RFC-768, USC/Information
  2207.        Sciences Institute, August 1980.
  2208.  
  2209.    7.  Mills, D., "Time Synchronization in DCNET Hosts", IEN-173, COMSAT
  2210.        Laboratories, February 1981.
  2211.  
  2212.    8.  Mills, D., "DCNET Internet Clock Service", RFC-778, COMSAT
  2213.        Laboratories, April 1981.
  2214.  
  2215.    9.  Su, Z., "A Specification of the Internet Protocol (IP) Timestamp
  2216.        Option", RFC-781, SRI International, May 1981.
  2217.  
  2218.    10. Defense Advanced Research Projects Agency, "Internet Protocol",
  2219.        RFC-791, USC/Information Sciences Institute, September 1981.
  2220.  
  2221.    11. Defense Advanced Research Projects Agency, "Internet Control
  2222.        Message Protocol", RFC-792, USC/Information Sciences Institute,
  2223.        September 1981.
  2224.  
  2225.    12. Postel, J., "Daytime Protocol", RFC-867, USC/Information Sciences
  2226.        Institute, May 1983.
  2227.  
  2228.    13. Postel, J., "Time Protocol", RFC-868, USC/Information Sciences
  2229.        Institute, May 1983.
  2230.  
  2231.    14. Mills, D., "Internet Delay Experiments", RFC-889, M/A-COM
  2232.        Linkabit, December 1983.
  2233.  
  2234.  
  2235.  
  2236. Mills                                                          [Page 40]
  2237.  
  2238. RFC 1059                 Network Time Protocol                 July 1988
  2239.  
  2240.  
  2241.    15. Mills, D., "DCN Local-Network Protocols", RFC-891, M/A-COM
  2242.        Linkabit, December 1983.
  2243.  
  2244.    16. Gusella, R., and S. Zatti, "TEMPO - A Network Time Controller for
  2245.        a Distributed Berkeley UNIX System", IEEE Distributed Processing
  2246.        Technical Committee Newsletter 6, No. SI-2, pgs. 7-15, June 1984.
  2247.        Also in: Proc.  Summer 1984 USENIX, Salt Lake City, June 1984.
  2248.  
  2249.    17. Halpern, J., Simons, B., Strong, R., and D. Dolly, "Fault-
  2250.        Tolerant Clock Synchronization", Proc. Third Annual ACM Symposium
  2251.        on Principles of Distributed Computing, pgs. 89-102, August 1984.
  2252.  
  2253.    18. Lundelius, J., and N. Lynch, "A New Fault-Tolerant Algorithm for
  2254.        Clock Synchronization:, Proc. Third Annual ACM Symposium on
  2255.        Principles of Distributed Computing, pgs. 75-88, August 1984.
  2256.  
  2257.    19. Lamport, L., and P. Melliar-Smith "Synchronizing Clocks in the
  2258.        Presence of Faults", JACM 32, No. 1, pgs. 52-78, January 1985.
  2259.  
  2260.    20. Gusella, R., and S. Zatti, "The Berkeley UNIX 4.3BSD Time
  2261.        Synchronization Protocol: Protocol Specification", Technical
  2262.        Report UCB/CSD 85/250, University of California, Berkeley, June
  2263.        1985.
  2264.  
  2265.    21. Marzullo, K., and S. Owicki, "Maintaining the Time in a
  2266.        Distributed System", ACM Operating Systems Review 19, No. 3, pgs.
  2267.        44-54, July 1985.
  2268.  
  2269.    22. Mills, D., "Algorithms for Synchronizing Network Clocks", RFC-
  2270.        956, M/A-COM Linkabit, September 1985.
  2271.  
  2272.    23. Mills, D., "Experiments in Network Clock Synchronization", RFC-
  2273.        957, M/A-COM Linkabit, September 1985.
  2274.  
  2275.    24. Mills, D., "Network Time Protocol (NTP)", RFC-958, M/A-COM
  2276.        Linkabit, September 1985.
  2277.  
  2278.    25. Gusella, R., and S. Zatti, "An Election Algorithm for a
  2279.        Distributed Clock Synchronization Program", Technical Report
  2280.        UCB/CSD 86/275, University of California, Berkeley, December
  2281.        1985.
  2282.  
  2283.    26. Sams, H., "Reference Data for Engineers:  Radio, Electronics,
  2284.        Computer and Communications (Seventh Edition)", Indianapolis,
  2285.        1985.
  2286.  
  2287.    27. Schneider, F., "A Paradigm for Reliable Clock Synchronization",
  2288.        Technical Report TR 86-735, Cornell University, February 1986.
  2289.  
  2290.  
  2291.  
  2292. Mills                                                          [Page 41]
  2293.  
  2294. RFC 1059                 Network Time Protocol                 July 1988
  2295.  
  2296.  
  2297.    28. Tripathi, S., and S. Chang, "ETempo:  A Clock Synchronization
  2298.        Algorithm for Hierarchical LANs - Implementation and
  2299.        Measurements", Systems Research Center Technical Report TR-86-48,
  2300.        University of Maryland, 1986.
  2301.  
  2302.    29. Bertsekas, D., and R.  Gallager, "Data Networks", Prentice-Hall,
  2303.        Englewood Cliffs, NJ, 1987.
  2304.  
  2305.    30. Srikanth, T., and S. Toueg. "Optimal Clock Synchronization", JACM
  2306.        34, No. 3, pgs. 626-645, July 1987.
  2307.  
  2308.    31. Rickert, N., "Non Byzantine Clock Synchronization - A Programming
  2309.        Experiment", ACM Operating Systems Review 22, No. 1, pgs. 73-78,
  2310.        January 1988.
  2311.  
  2312.  
  2313.  
  2314.  
  2315.  
  2316.  
  2317.  
  2318.  
  2319.  
  2320.  
  2321.  
  2322.  
  2323.  
  2324.  
  2325.  
  2326.  
  2327.  
  2328.  
  2329.  
  2330.  
  2331.  
  2332.  
  2333.  
  2334.  
  2335.  
  2336.  
  2337.  
  2338.  
  2339.  
  2340.  
  2341.  
  2342.  
  2343.  
  2344.  
  2345.  
  2346.  
  2347.  
  2348. Mills                                                          [Page 42]
  2349.  
  2350. RFC 1059                 Network Time Protocol                 July 1988
  2351.  
  2352.  
  2353. Appendix A.  UDP Header Format
  2354.  
  2355.    An NTP packet consists of the UDP header followed by the NTP data
  2356.    portion.  The format of the UDP header and the interpretation of its
  2357.    fields are described in [6] and are not part of the NTP
  2358.    specification.  They are shown below for completeness.
  2359.  
  2360.     0                   1                   2                   3
  2361.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  2362.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2363.    |          Source Port          |       Destination Port        |
  2364.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2365.    |            Length             |           Checksum            |
  2366.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2367.  
  2368.    Source Port
  2369.  
  2370.           UDP source port number. In the case of a client request this
  2371.           field is assigned by the client host, while for a server reply
  2372.           it is copied from the Destination Port field of the client
  2373.           request. In the case of symmetric mode, both the Source Port
  2374.           and Destination Port fields are assigned the NTP service-port
  2375.           number 123.
  2376.  
  2377.    Destination Port
  2378.  
  2379.           UDP destination port number. In the case of a client request
  2380.           this field is assigned the NTP service-port number 123, while
  2381.           for a server reply it is copied from the Source Port field of
  2382.           the client request. In the case of symmetric mode, both the
  2383.           Source Port and Destination Port fields are assigned the NTP
  2384.           service-port number 123.
  2385.  
  2386.    Length
  2387.  
  2388.           Length of the request or reply, including UDP header, in
  2389.           octets
  2390.  
  2391.    Checksum
  2392.  
  2393.           Standard UDP checksum
  2394.  
  2395.  
  2396.  
  2397.  
  2398.  
  2399.  
  2400.  
  2401.  
  2402.  
  2403.  
  2404. Mills                                                          [Page 43]
  2405.  
  2406. RFC 1059                 Network Time Protocol                 July 1988
  2407.  
  2408.  
  2409. Appendix B.  NTP Data Format - Version 1
  2410.  
  2411.    The format of the NTP data portion, which immediately follows the UDP
  2412.    header, is shown below along with a description of its fields.
  2413.  
  2414.  
  2415.     0                   1                   2                   3
  2416.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  2417.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2418.    |LI | VN  |0 0 0|    Stratum    |      Poll     |   Precision   |
  2419.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2420.    |                     Synchronizing Distance                    |
  2421.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2422.    |                     Estimated Drift Rate                      |
  2423.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2424.    |                  Reference Clock Identifier                   |
  2425.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2426.    |                                                               |
  2427.    |                 Reference Timestamp (64 bits)                 |
  2428.    |                                                               |
  2429.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2430.    |                                                               |
  2431.    |                 Originate Timestamp (64 bits)                 |
  2432.    |                                                               |
  2433.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2434.    |                                                               |
  2435.    |                  Receive Timestamp (64 bits)                  |
  2436.    |                                                               |
  2437.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2438.    |                                                               |
  2439.    |                  Transmit Timestamp (64 bits)                 |
  2440.    |                                                               |
  2441.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  2442.  
  2443.    Leap Indicator (LI)
  2444.  
  2445.           Two-bit code warning of impending leap-second to be inserted
  2446.           at the end of the last day of the current month. Bits are
  2447.           coded as follows:
  2448.  
  2449.                     00      no warning
  2450.                     01      +1 second (following minute has 61 seconds)
  2451.                     10      -1 second (following minute has 59 seconds)
  2452.                     11      alarm condition (clock not synchronized)
  2453.  
  2454.  
  2455.  
  2456.  
  2457.  
  2458.  
  2459.  
  2460. Mills                                                          [Page 44]
  2461.  
  2462. RFC 1059                 Network Time Protocol                 July 1988
  2463.  
  2464.  
  2465.    Version Number (VN)
  2466.  
  2467.           Three-bit code indicating the version number, currently one
  2468.           (1).
  2469.  
  2470.    Reserved
  2471.  
  2472.           Three-bit field consisting of all zeros and reserved for
  2473.           future use.
  2474.  
  2475.    Stratum
  2476.  
  2477.           Integer identifying stratum level of local clock. Values are
  2478.           defined as follows:
  2479.  
  2480.                     0       unspecified
  2481.                     1       primary reference (e.g., radio clock)
  2482.                     2...n   secondary reference (via NTP)
  2483.  
  2484.    Poll
  2485.  
  2486.           Signed integer indicating the maximum interval between
  2487.           successive messages, in seconds to the nearest power of two.
  2488.  
  2489.    Precision
  2490.  
  2491.           Signed integer indicating the precision of the local clock, in
  2492.           seconds to the nearest power of two.
  2493.  
  2494.    Synchronizing Distance
  2495.  
  2496.           Fixed-point number indicating the estimated roundtrip delay to
  2497.           the primary synchronizing source, in seconds with fraction
  2498.           point between bits 15 and 16.
  2499.  
  2500.    Estimated Drift Rate
  2501.  
  2502.           Fixed-point number indicating the estimated drift rate of the
  2503.           local clock, in dimensionless units with fraction point to the
  2504.           left of the most significant bit.
  2505.  
  2506.    Reference Clock Identifier
  2507.  
  2508.           Code identifying the particular reference clock. In the case
  2509.           of type 0 (unspecified) or type 1 (primary reference), this is
  2510.           a left-justified, zero-filled ASCII string, for example:
  2511.  
  2512.  
  2513.  
  2514.  
  2515.  
  2516. Mills                                                          [Page 45]
  2517.  
  2518. RFC 1059                 Network Time Protocol                 July 1988
  2519.  
  2520.  
  2521.                     Type    Code    Meaning
  2522.                     ---------------------------------------------------
  2523.                     0       DCN     Determined by DCN routing algorithm
  2524.                     1       WWVB    WWVB radio clock (60 kHz)
  2525.                     1       GOES    GOES satellite clock (468 MHz)
  2526.                     1       WWV     WWV radio clock (5/10/15 MHz)
  2527.                     (and others as necessary)
  2528.  
  2529.           In the case of type 2 and greater (secondary reference), this
  2530.           is the 32-bit Internet address of the reference host.
  2531.  
  2532.    Reference Timestamp
  2533.  
  2534.           Local time at which the local clock was last set or corrected.
  2535.  
  2536.    Originate Timestamp
  2537.  
  2538.           Local time at which the request departed the client host for
  2539.           the service host.
  2540.  
  2541.    Receive Timestamp
  2542.  
  2543.           Local time at which the request arrived at the service host.
  2544.  
  2545.    Transmit Timestamp
  2546.  
  2547.           Local time at which the reply departed the service host for
  2548.           the client host.
  2549.  
  2550.  
  2551.  
  2552.  
  2553.  
  2554.  
  2555.  
  2556.  
  2557.  
  2558.  
  2559.  
  2560.  
  2561.  
  2562.  
  2563.  
  2564.  
  2565.  
  2566.  
  2567.  
  2568.  
  2569.  
  2570.  
  2571.  
  2572. Mills                                                          [Page 46]
  2573.  
  2574. RFC 1059                 Network Time Protocol                 July 1988
  2575.  
  2576.  
  2577. Appendix C.  Timeteller Experiments
  2578.  
  2579.    In order to update data collected in June 1985 and reported in RFC-
  2580.    957, a glorious three-day experiment was carried out in January 1988
  2581.    with all the hosts and gateways listed in the NIC data base.  Four
  2582.    packets were sent at five-second intervals to each host and gateway
  2583.    using UDP/NTP, UDP/TIME and ICMP/TIMESTAMP protocols and the clock
  2584.    offsets (in milliseconds) for each protocol averaged with respect to
  2585.    local time, which is synchronized via NTP to a radio-clock host.
  2586.    While the ICMP/TIMESTAMP protocol has much finer granularity
  2587.    (milliseconds) than UDP/TIME (seconds), it has no provisions for the
  2588.    date, so is not suitable as a time-synchronization protocol;
  2589.    however, it was included in the experiments both as a sanity check
  2590.    and in order to assess the precision of measurement.
  2591.  
  2592.    In the latest survey of 5498 hosts and 224 gateways, 46 responded to
  2593.    UDP/NTP requests, 1158 to UDP/TIME and 1963 to ICMP/TIMESTAMP.  By
  2594.    contrast, in the 1985 survey of 1775 hosts and 110 gateways, 163
  2595.    responded to UDP/TIME requests and 504 to ICMP/TIMESTAMP.  At that
  2596.    time there were no UDP/NTP implementations.  There are many more
  2597.    hosts and gateways listed in the rapidly growing domain-name system,
  2598.    but not listed in the NIC data base, and therefore not surveyed.  The
  2599.    results of the survey are given in Table C.1, which shows for each of
  2600.    the three protocols the error X for which the distribution function
  2601.    P[x =< X] has the value shown.
  2602.  
  2603.            P[x=<X] UDP/NTP         UDP/TIME        ICMP/TIMESTAMP
  2604.            ------------------------------------------------------
  2605.            .1      11              4632            5698
  2606.            .2      37              18238           27965
  2607.            .3      66              38842           68596
  2608.            .4      177             68213           127367
  2609.            .5      364             126232          201908
  2610.            .6      567             195950          285092
  2611.            .7      3466            267119          525509
  2612.            .8      20149           422129          2.91426E+06
  2613.            .9      434634          807135          5.02336E+07
  2614.            1       1.17971E+09     1.59524E+09     2.11591E+09
  2615.  
  2616.                      Table C.1. Distribution Functions
  2617.  
  2618.    It can be seen that ten percent of the UDP/NTP responses show errors
  2619.    of 11 milliseconds or less and that ten percent of the UDP/TIME
  2620.    responses show errors greater than 807135 milliseconds (about 13
  2621.    minutes).  Fifty percent of the UDP/NTP timetellers are within 364
  2622.    milliseconds, while fifty percent of the UDP/TIME tellers are within
  2623.    126232 milliseconds (just over two minutes).  Surprisingly,
  2624.    ICMP/TIMESTAMP responses show errors even larger than UDP/TIME.
  2625.  
  2626.  
  2627.  
  2628. Mills                                                          [Page 47]
  2629.  
  2630. RFC 1059                 Network Time Protocol                 July 1988
  2631.  
  2632.  
  2633.    However, the maximum error shown in all three protocols exceeded the
  2634.    range that could be recorded, in this case about 12 days.  Clearly,
  2635.    there are good timetellers and bad.
  2636.  
  2637.  
  2638.  
  2639.  
  2640.  
  2641.  
  2642.  
  2643.  
  2644.  
  2645.  
  2646.  
  2647.  
  2648.  
  2649.  
  2650.  
  2651.  
  2652.  
  2653.  
  2654.  
  2655.  
  2656.  
  2657.  
  2658.  
  2659.  
  2660.  
  2661.  
  2662.  
  2663.  
  2664.  
  2665.  
  2666.  
  2667.  
  2668.  
  2669.  
  2670.  
  2671.  
  2672.  
  2673.  
  2674.  
  2675.  
  2676.  
  2677.  
  2678.  
  2679.  
  2680.  
  2681.  
  2682.  
  2683.  
  2684. Mills                                                          [Page 48]
  2685.  
  2686. RFC 1059                 Network Time Protocol                 July 1988
  2687.  
  2688.  
  2689. Appendix D.  Evaluation of Filtering Algorithms
  2690.  
  2691.    A number of algorithms for deglitching and filtering time-offset data
  2692.    were described in RFC-956.  These fall in two classes:  majority-
  2693.    subset algorithms, which attempt to separate good subsets from bad by
  2694.    comparing their means, and clustering algorithms, which attempt to
  2695.    improve the estimate by repeatedly casting out outlyers.  The former
  2696.    class was suggested as a technique to select the best (i.e.  the most
  2697.    reliable) clocks from a population, while the latter class was
  2698.    suggested as a technique to improve the offset estimate for a single
  2699.    clock given a series of observations.
  2700.  
  2701.    Following publication of RFC-956 and after further development and
  2702.    experimentation using typical Internet paths, a better algorithm was
  2703.    found for casting out outlyers from a continuous stream of offset
  2704.    observations spaced at intervals in the order of minutes.  The
  2705.    algorithm is described as a variant of a median filter, in which a
  2706.    window consisting of the last n sample offsets is continuously
  2707.    updated and the median sample selected as the estimate.  However, in
  2708.    the modified algorithm the outlyer (sample furthest from the median)
  2709.    is then discarded and the entire process repeated until only a single
  2710.    sample offset is left, which is then selected as the estimate.
  2711.  
  2712.    The modified algorithm was found to be more resistant to glitches and
  2713.    to provide a more accurate estimate than the unmodified one.  It has
  2714.    been implemented in the NTP daemons developed for the Fuzzball and
  2715.    Unix operating systems and been in regular operation for about two
  2716.    years.  However, recent experiments have shown there is an even
  2717.    better one which provides comparable accuracy together with a much
  2718.    lower computational burden.  The key to the new algorithm became
  2719.    evident through an examination of scatter diagrams plotting sample
  2720.    offset versus roundtrip delay.
  2721.  
  2722.    To see how a scatter diagram is constructed, it will be useful to
  2723.    consider how offsets and delays are computed.  Number the times of
  2724.    sending and receiving NTP messages as shown in Figure D.1 and let i
  2725.    be an even integer.  Then the timestamps t(i-3), t(i-2) and t(i-1)
  2726.    and t(i) are sufficient to calculate the offset and delay of each
  2727.    peer relative to the other.
  2728.  
  2729.  
  2730.  
  2731.  
  2732.  
  2733.  
  2734.  
  2735.  
  2736.  
  2737.  
  2738.  
  2739.  
  2740. Mills                                                          [Page 49]
  2741.  
  2742. RFC 1059                 Network Time Protocol                 July 1988
  2743.  
  2744.  
  2745.                    Peer 1                    Peer 2
  2746.                         |                    |
  2747.                    t(1) |------------------->| t(2)
  2748.                         |                    |
  2749.                    t(4) |<-------------------| t(3)
  2750.                         |                    |
  2751.                    t(5) |------------------->| t(6)
  2752.                         |                    |
  2753.                    t(8) |<-------------------| t(7)
  2754.                         |                    |
  2755.                                  ...
  2756.  
  2757.                  Figure D.1. Calculating Delay and Offset
  2758.  
  2759.    The roundtrip delay d and clock offset c of the receiving peer
  2760.    relative to the sending peer are:
  2761.  
  2762.  
  2763.                    d = (t(i) - t(i-3)) - (t(i-1) - t(i-2))
  2764.                 c = [(t(i-2) - t(i-3)) + (t(i-1) - t(i))]/2 .
  2765.  
  2766.    Two implicit assumptions in the above are that the delay distribution
  2767.    is independent of direction and that the intrinsic drift rates of the
  2768.    client and server clocks are small and close to the same value.  If
  2769.    this is the case the scatter diagram would show the samples
  2770.    concentrated about a horizontal line extending from the point (d,c)
  2771.    to the right.  However, this is not generally the case.  The typical
  2772.    diagram shows the samples dispersed in a wedge with apex (d,c) and
  2773.    opening to the right.  The limits of the wedge are determined by
  2774.    lines extending from (d,c) with slopes +0.5 and -0.5, which
  2775.    correspond to the locus of points as the delay in one direction
  2776.    increases while the delay in the other direction does not.  In some
  2777.    cases the points are concentrated along these two extrema lines, with
  2778.    relatively few points remaining within the opening of the wedge,
  2779.    which would correspond to increased delays on both directions.
  2780.  
  2781.    Upon reflection, the reason for the particular dispersion shown in
  2782.    the scatter diagram is obvious.  Packet-switching nets are most often
  2783.    operated with relatively small mean queue lengths in the order of
  2784.    one, which means the queues are often idle for relatively long
  2785.    periods.  In addition, the routing algorithm most often operates to
  2786.    minimize the number of packet-switch hops and thus the number of
  2787.    queues.  Thus, not only is the probability that an arriving NTP
  2788.    packet finds a busy queue in one direction reasonably low, but the
  2789.    probability of it finding a busy queue in both directions is even
  2790.    lower.
  2791.  
  2792.    From the above discussion one would expect that, at low utilizations
  2793.  
  2794.  
  2795.  
  2796. Mills                                                          [Page 50]
  2797.  
  2798. RFC 1059                 Network Time Protocol                 July 1988
  2799.  
  2800.  
  2801.    and hop counts the points should be concentrated about the apex of
  2802.    the wedge and begin to extend rightward along the extrema lines as
  2803.    the utilizations and hop counts increase.  As the utilizations and
  2804.    hop counts continue to increase, the points should begin to fill in
  2805.    the wedge as it expands even further rightward.  This behavior is in
  2806.    fact what is observed on typical Internet paths involving ARPANET,
  2807.    NSFNET and other nets.
  2808.  
  2809.    These observations cast doubt on the median-filter approach as a good
  2810.    way to cast out offset outlyers and suggests another approach which
  2811.    might be called a minimum filter.  From the scatter diagrams it is
  2812.    obvious that the best offset samples occur at the lower delays.
  2813.    Therefore, an appropriate technique would be simply to select from
  2814.    the n most recent samples the sample with lowest delay and use its
  2815.    associated offset as the estimate.  An experiment was designed to
  2816.    test this technique using measurements between selected hosts
  2817.    equipped with radio clocks, so that delays and offsets could be
  2818.    determined independent of the measurement procedure itself.
  2819.  
  2820.    The raw delays and offsets were measured by NTP from hosts at U
  2821.    Maryland (UMD) and U Delaware (UDEL) via net paths to each other and
  2822.    other hosts at Ford Research (FORD), Information Sciences Institute
  2823.    (ISI) and National Center for Atmospheric Research (NCAR).  For the
  2824.    purposes here, all hosts can be assumed synchronized to within a few
  2825.    milliseconds to NBS time, so that the delays and offsets reflect only
  2826.    the net paths themselves.
  2827.  
  2828.    The results of the measurements are given in Table D.1 (UMD) and
  2829.    Table D.2 (UDEL), which show for each of the paths the error X for
  2830.    which the distribution function P[x =< X] has the value shown.  Note
  2831.    that the values of the distribution function are shown by intervals
  2832.    of decreasing size as the function increases, so that its behavior in
  2833.    the interesting regime of low error probability can be more
  2834.    accurately determined.
  2835.  
  2836.  
  2837.  
  2838.  
  2839.  
  2840.  
  2841.  
  2842.  
  2843.  
  2844.  
  2845.  
  2846.  
  2847.  
  2848.  
  2849.  
  2850.  
  2851.  
  2852. Mills                                                          [Page 51]
  2853.  
  2854. RFC 1059                 Network Time Protocol                 July 1988
  2855.  
  2856.  
  2857.     UMD    FORD    ISI     NCAR          UMD    FORD    ISI     NCAR
  2858.     Delay  1525    2174    1423          Offset 1525    2174    1423
  2859.     ---------------------------          ---------------------------
  2860.     .1     493     688     176           .1     2       17      1
  2861.     .2     494     748     179           .2     4       33      2
  2862.     .3     495     815     187           .3     9       62      3
  2863.     .4     495     931     205           .4     18      96      8
  2864.     .5     497     1013    224           .5     183     127     13
  2865.     .6     503     1098    243           .6     4.88E+8 151     20
  2866.     .7     551     1259    265           .7     4.88E+8 195     26
  2867.     .8     725     1658    293           .8     4.88E+8 347     35
  2868.     .9     968     2523    335           .9     4.88E+8 775     53
  2869.     .99    1409    6983    472           .99    4.88E+8 2785    114
  2870.     .999   14800   11464   22731         .999   4.88E+8 5188    11279
  2871.     1      18395   15892   25647         1      4.88E+8 6111    12733
  2872.  
  2873.               Table D.1. Delay and Offset Measurements (UMD)
  2874.  
  2875.            UDEL   FORD    UMD     ISI     NCAR
  2876.            Delay  2986    3442    3215    2756
  2877.            -----------------------------------
  2878.            .1     650     222     411     476
  2879.            .2     666     231     436     512
  2880.            .3     692     242     471     554
  2881.            .4     736     256     529     594
  2882.            .5     787     272     618     648
  2883.            .6     873     298     681     710
  2884.            .7     1013    355     735     815
  2885.            .8     1216    532     845     1011
  2886.            .9     1836    1455    1019    1992
  2887.            .99    4690    3920    1562    4334
  2888.            .999   15371   6132    2387    11234
  2889.            1      21984   8942    4483    21427
  2890.  
  2891.                    Table D.2.a Delay Measurements (UDEL)
  2892.  
  2893.  
  2894.  
  2895.  
  2896.  
  2897.  
  2898.  
  2899.  
  2900.  
  2901.  
  2902.  
  2903.  
  2904.  
  2905.  
  2906.  
  2907.  
  2908. Mills                                                          [Page 52]
  2909.  
  2910. RFC 1059                 Network Time Protocol                 July 1988
  2911.  
  2912.  
  2913.            UDEL   FORD    UMD     ISI     NCAR
  2914.            Offset 2986    3442    3215    2756
  2915.            -----------------------------------
  2916.            .1     83      2       16      12
  2917.            .2     96      5       27      24
  2918.            .3     108     9       36      36
  2919.            .4     133     13      48      51
  2920.            .5     173     20      67      69
  2921.            .6     254     30      93      93
  2922.            .7     429     51      130     133
  2923.            .8     1824    133     165     215
  2924.            .9     4.88E+8 582     221     589
  2925.            .99    4.88E+8 1757    539     1640
  2926.            .999   4.88E+8 2945    929     5278
  2927.            1      5.63E+8 4374    1263    10425
  2928.  
  2929.                   Table D.2.b Offset Measurements (UDEL)
  2930.  
  2931.    The results suggest that accuracies less than a few seconds can
  2932.    usually be achieved for all but one percent of the measurements, but
  2933.    that accuracies degrade drastically when the remaining measurements
  2934.    are included.  Note that in the case of the UMD measurements to FORD
  2935.    almost half the measurements showed gross errors, which was due to
  2936.    equipment failure at that site.  These data were intentionally left
  2937.    in the sample set to see how well the algorithms dealt with the
  2938.    problem.
  2939.  
  2940.    The next two tables compare the results of minimum filters (Table
  2941.    D.3) and median filters (Table D.4) for various n when presented with
  2942.    the UMD - - NCAR raw sample data.  The results show consistently
  2943.    lower errors for the minimum filter when compared with the median
  2944.    filter of nearest value of n.  Perhaps the most dramatic result of
  2945.    both filters is the greatly reduced error at the upper end of the
  2946.    range.  In fact, using either filter with n at least three results in
  2947.    no errors greater than 100 milliseconds.
  2948.  
  2949.  
  2950.  
  2951.  
  2952.  
  2953.  
  2954.  
  2955.  
  2956.  
  2957.  
  2958.  
  2959.  
  2960.  
  2961.  
  2962.  
  2963.  
  2964. Mills                                                          [Page 53]
  2965.  
  2966. RFC 1059                 Network Time Protocol                 July 1988
  2967.  
  2968.  
  2969.                            Filter Samples
  2970.                    1       2       4       8       16
  2971.            P[x=<X] 1423    1422    1422    1420    1416
  2972.            - --------------------------------------------
  2973.             .1     1       1       1       0       0
  2974.             .2     2       1       1       1       1
  2975.             .3     3       2       1       1       1
  2976.             .4     8       2       2       1       1
  2977.             .5     13      5       2       2       1
  2978.             .6     20      10      3       2       2
  2979.             .7     26      15      6       2       2
  2980.             .8     35      23      11      4       2
  2981.             .9     53      33      20      9       3
  2982.             .99    114     62      43      28      23
  2983.             .999   11279   82      57      37      23
  2984.             1      12733   108     59      37      23
  2985.  
  2986.                          Table D.3. Minimum Filter
  2987.                                (UMD - NCAR)
  2988.  
  2989.                            Filter Samples
  2990.                            3       7       15
  2991.                    P[x=<X] 1423    1423    1423
  2992.                      ----------------------------
  2993.                     .1     2       2       2
  2994.                     .2     2       4       5
  2995.                     .3     5       8       8
  2996.                     .4     10      11      11
  2997.                     .5     13      14      14
  2998.                     .6     18      17      16
  2999.                     .7     23      21      19
  3000.                     .8     28      25      23
  3001.                     .9     36      30      27
  3002.                     .99    64      46      35
  3003.                     .999   82      53      44
  3004.                     1      82      60      44
  3005.  
  3006.                          Table D.4. Median Filter
  3007.                                (UMD - NCAR)
  3008.  
  3009.    While the UMD - NCAR data above represented a path across the NSFNET
  3010.    Backbone, which normally involves only a few hops via Ethernets and
  3011.    56-Kbps links, the UDEL - NCAR path involves additional ARPANET hops,
  3012.    which can contribute substantial additional delay dispersion.  The
  3013.    following Table D.5.  shows the results of a minimum filter for
  3014.    various n when presented with the UDEL - NCAR raw sample data.  The
  3015.    range of error is markedly greater than the UMD - NCAR path above,
  3016.    especially near the upper end of the distribution function.
  3017.  
  3018.  
  3019.  
  3020. Mills                                                          [Page 54]
  3021.  
  3022. RFC 1059                 Network Time Protocol                 July 1988
  3023.  
  3024.  
  3025.                                 Filter Samples
  3026.                         1       2       4       8       16
  3027.                 P[x=<X] 2756    2755    2755    2753    2749
  3028.                 --------------------------------------------
  3029.                  .1     12      9       8       7       6
  3030.                  .2     24      19      16      14      14
  3031.                  .3     36      27      22      20      19
  3032.                  .4     51      36      29      25      23
  3033.                  .5     69      47      36      30      27
  3034.                  .6     93      61      44      35      32
  3035.                  .7     133     80      56      43      35
  3036.                  .8     215     112     75      53      43
  3037.                  .9     589     199     111     76      63
  3038.                  .99    1640    1002    604     729     315
  3039.                  .999   5278    1524    884     815     815
  3040.                  1      10425   5325    991     835     815
  3041.  
  3042.                    Table D.5. Minimum Filter (UDEL - NCAR)
  3043.  
  3044.    Based on these data, the minimum filter was selected as the standard
  3045.    algorithm.  Since its performance did not seem to much improve for
  3046.    values of n above eight, this value was chosen as the standard.
  3047.    Network Time Protocol (Version 1): Specification and Implementation.
  3048.  
  3049.  
  3050.  
  3051.  
  3052.  
  3053.  
  3054.  
  3055.  
  3056.  
  3057.  
  3058.  
  3059.  
  3060.  
  3061.  
  3062.  
  3063.  
  3064.  
  3065.  
  3066.  
  3067.  
  3068.  
  3069.  
  3070.  
  3071.  
  3072.  
  3073.  
  3074.  
  3075.  
  3076. Mills                                                          [Page 55]
  3077.  
  3078. RFC 1059                 Network Time Protocol                 July 1988
  3079.  
  3080.  
  3081. Appendix E.  NTP Synchronization Networks
  3082.  
  3083.    This section discusses net configuration issues for implementing a
  3084.    ubiquitous NTP service in the Internet system.  Section E.1 describes
  3085.    the NTP primary service net now in operation, including an analysis
  3086.    of failure scenarios.  Section E.2 suggests how secondary service
  3087.    nets, which obtain wholesale time from the primary service net, can
  3088.    be configured to deliver accurate and reliable retail time to the
  3089.    general host population.
  3090.  
  3091. E.1.  Primary Service Network
  3092.  
  3093.    The primary service net consists of five primary servers, each of
  3094.    which is synchronized via radio or satellite to a national time
  3095.    standard and thus operates at stratum one.  Each server consists of
  3096.    an LSI-11 Fuzzball, a WWVB or GOES radio clock and one or more net
  3097.    interfaces.  Some servers provide switching and gateway services as
  3098.    well.  Table E.1 shows the name, Internet address, type of clock,
  3099.    operating institution and identifying code.
  3100.  
  3101. Name          Address         Clock   Operating Institution and (Code)
  3102. ----------------------------------------------------------------------
  3103. DCN5.ARPA     128.4.0.5       WWVB    U Delaware, Newark, DE (UDEL)
  3104. FORD1.ARPA    128.5.0.1       GOES    Ford Research, Dearborn, MI
  3105.                                         (FORD)
  3106. NCAR.NSF.NET  128.116.64.3    WWVB    National Center for Atmospheric
  3107.                                         Research, Boulder, CO (NCAR)
  3108. UMD1.UMD.EDU  128.8.10.1      WWVB    U Maryland, College Park, MD
  3109.                                         (UMD)
  3110. WWVB.ISI.EDU  128.9.2.129     WWVB    USC Information Sciences
  3111.                                         Institute, Marina del Rey, CA
  3112.                                         (ISI)
  3113.  
  3114.                        Table E.1. Primary Servers
  3115.  
  3116.    Figure E.1 shows how the five primary servers are interconnected as
  3117.    NTP peers.  Note that each server actively probes two other servers
  3118.    (along the direction of the arrows), which means these probes will
  3119.    continue even if one or both of the two probed servers are down.  On
  3120.    the other hand, each server is probed by two other servers, so that
  3121.    the result, assuming all servers are up, is that every server peers
  3122.    with every other server.
  3123.  
  3124.  
  3125.  
  3126.  
  3127.  
  3128.  
  3129.  
  3130.  
  3131.  
  3132. Mills                                                          [Page 56]
  3133.  
  3134. RFC 1059                 Network Time Protocol                 July 1988
  3135.  
  3136.  
  3137.                +------------------------------------------------+
  3138.                V                                                |
  3139.            +--------+              +--------+              +--------+
  3140.            |        |<-------------|        |<-------------|        |
  3141.            |  NCAR  |              |  ISI   |              |  FORD  |
  3142.            |        |----+      +--|        |<--+    +---->|        |
  3143.            +--------+    |      |  +--------+   |    |     +--------+
  3144.                |         |      |               |    |          A
  3145.                |     +---|------|---------------|----+          |
  3146.                |     |   |      |               |               |
  3147.                |     |   +------|---------------|---------+     |
  3148.                |     |          |               |         |     |
  3149.                |     |          |               |         V     |
  3150.                |   +--------+   |               |  +--------+   |
  3151.                |   |        |<--+               +--|        |   |
  3152.                +-->|  UMD   |                      |  UDEL  |---+
  3153.                    |        |--------------------->|        |
  3154.                    +--------+                      +--------+
  3155.  
  3156.                     Figure E.1. Primary Service Network
  3157.  
  3158.    All of the five primary servers shown are directly connected to a
  3159.    radio clock and thus normally operate at stratum one.  However, if
  3160.    the radio clock itself becomes disabled or the propagation path to
  3161.    its synchronizing source fails, then the server drops to stratum two
  3162.    and synchronizes via NTP with its neighbor at the smallest
  3163.    synchronizing distance.  If a radio clock appears to operate
  3164.    correctly but delivers incorrect time (falseticker), the server may
  3165.    remain synchronized to the clock.  However, gross discrepancies will
  3166.    become apparent via the NTP peer paths, which will ordinarily result
  3167.    in an operator alarm.
  3168.  
  3169.    Assume that, if a radio clock appears up, it is a truechimer;
  3170.    otherwise, the clock appears down.  Then the above configuration will
  3171.    continue to provide correct time at all primary servers as long as at
  3172.    least one radio clock is up, all servers are up and the servers
  3173.    remain connected to each other through the net.  The fact that the
  3174.    graph and all of its subgraphs are completely connected lends an
  3175.    incredible resilience to the configuration.
  3176.  
  3177.    If some radio clocks appear up but are in fact falsetickers, the
  3178.    primary servers connected to those clocks will not provide correct
  3179.    time.  However, as the consequents of the voting procedure and
  3180.    complete connectivity of the graph and its subgraphs, any combination
  3181.    of two falsetickers or of one falseticker and one down server will be
  3182.    detected by their truechimer neighbors.
  3183.  
  3184.  
  3185.  
  3186.  
  3187.  
  3188. Mills                                                          [Page 57]
  3189.  
  3190. RFC 1059                 Network Time Protocol                 July 1988
  3191.  
  3192.  
  3193. E.2.  Secondary Service Networks
  3194.  
  3195.    A secondary server operating at stratum n > 1 ordinarily obtains
  3196.    synchronization using at least three peer paths, two with servers at
  3197.    stratum n-1 and one or more with servers at stratum n.  In the most
  3198.    robust configurations a set of servers agree to provide backup
  3199.    service for each other, so distribute some of their peer paths over
  3200.    stratum-(n-1) servers and others over stratum-n servers in the same
  3201.    set.  For instance, in the case of a stratum-2 service net with two
  3202.    secondary servers and the primary service net of Figure E.1, there
  3203.    are five possible configurations where each stratum-1 path ends on a
  3204.    different primary server.  Such configurations can survive the loss
  3205.    of three out of the four stratum-1 servers or net paths and will
  3206.    reject a single falseticker on one of the two stratum-1 paths for
  3207.    each server.
  3208.  
  3209.    Ordinary hosts can obtain retail time from primary or secondary
  3210.    service net using NTP in client/server mode, which does not require
  3211.    dedicated server resources as does symmetric mode.  It is anticipated
  3212.    that ordinary hosts will be quite close to a secondary server,
  3213.    perhaps on the same cable or local net, so that the frequency of NTP
  3214.    request messages need only be high enough, perhaps one per hour or
  3215.    two, to trim the drift from the local clock.
  3216.  
  3217.  
  3218.  
  3219.  
  3220.  
  3221.  
  3222.  
  3223.  
  3224.  
  3225.  
  3226.  
  3227.  
  3228.  
  3229.  
  3230.  
  3231.  
  3232.  
  3233.  
  3234.  
  3235.  
  3236.  
  3237.  
  3238.  
  3239.  
  3240.  
  3241.  
  3242.  
  3243.  
  3244. Mills                                                          [Page 58]
  3245.  
  3246.